Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Minimum Spanning Tree

  1. #1
    Junior Member
    Join Date
    Mar 2012
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Minimum Spanning Tree

    cw4.jpg

    *attacted image is my assignment questions

    1 Graph: {V, G}
    5 Vertices (V): {A, B, C, D, E}
    8 Edges (E): {AB, AC, AD, BC, BD, BE,CD, DE}


    Hi. I have some difficulty in my assignment which i have to get the minimum spanning tree from an undirected weighted graph. I have study the 2 algorithm prim and kruskal alogrithm but i only have a little knowledge on how it works. I need a clearer explaination.

    I do know how to start of with my assignment. how am i going to create a graph using java?(I just need to create a hardcoded graph shown in my assignment) what data structure i should use? what are the classes I need? How do i use the algoirthm and apply on my graph

    I am a beginner in Java and hope someone can assist me. Thanks in advance,

    currently I have a vertex class. what are the fields i should have? does it works like a TreeNode
    String name; // point A
    Vertex point1; //refer to Vertex that are connect to this instance
    Vertex point2; //refer to Vertex that are connect to this instance
    vertex point3; //refer to Vertex that are connect to this instance
    vertex point4; //refer to Vertex that are connect to this instance


    I have an edge class which will include 3 fields?
    String edgeName
    String vertex1 // one vertex
    String vertex2 // to another vertex
    int weight


    prim and kruskal alogrithm:
    http://www.cs.princeton.edu/courses/...ures/19MST.pdf

    difference: What are difference between Primes algorithm and Krushkals algorithm for finding the minimum spanning tree of a graph
    Last edited by Undertaker; March 17th, 2012 at 01:09 AM.


  2. #2
    Junior Member
    Join Date
    Mar 2012
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Minimum Spanning Tree

    guys i have a set of vertex and edges created.
    Vertex vertexA = new Vertex("A", "A");
    Vertex vertexB = new Vertex("B", "B");
    Vertex vertexC = new Vertex("C", "C");
    Vertex vertexD = new Vertex("D", "D");
    Vertex vertexE = new Vertex("E", "E");

    Edge e1 = new Edge("e1", vertexA, vertexB, 10);
    Edge e2 = new Edge("e2", vertexA, vertexC, 14);
    Edge e3 = new Edge("e3", vertexA, vertexD, 7);
    Edge e4 = new Edge("e4", vertexB, vertexC, 21);
    Edge e5 = new Edge("e5", vertexB, vertexD, 12);
    Edge e6 = new Edge("e6", vertexB, vertexE, 27);
    Edge e7 = new Edge("e7", vertexC, vertexD, 8);
    Edge e8 = new Edge("e8", vertexC, vertexE, 13);
    Edge e9 = new Edge("e9", vertexD, vertexE, 15);

    public class Vertex {
    final private String id;
    final private String name;
    .....
    public class Edge {
    private final String id;
    private final Vertex source;
    private final Vertex destination;
    private final int weight;
    // doesn't matter coz is an undirected graph so whichever vertex can be source or destination

    ......
    Last edited by Undertaker; March 17th, 2012 at 09:56 AM.

Similar Threads

  1. B+ tree
    By cms in forum Algorithms & Recursion
    Replies: 2
    Last Post: December 15th, 2011, 07:58 AM
  2. Minimum value of objects in ArrayList
    By Sputnik in forum Loops & Control Statements
    Replies: 2
    Last Post: October 23rd, 2010, 01:20 PM
  3. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  4. t:tree 2 an
    By smackdown90 in forum Web Frameworks
    Replies: 0
    Last Post: January 27th, 2010, 12:56 PM
  5. B+ Tree
    By mikesir87 in forum Java Theory & Questions
    Replies: 0
    Last Post: November 20th, 2009, 10:52 AM