Thread: 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

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

......