Krusal's Algorithm Introduction:
In this project you will need to implement Kruskal's algorithm. Watch the videos that I posted for a description of the algorithm. Your code should start by reading a text file that contains the edges and weights of a graph. For example, this graph:
will be described in a text file that looks like:
A,1,B,2,D,2,F
B,1,A,1,C,2,D
C,1,B,1,D,3,E
E,3,C,2,D,1,G
G,1,E,3,D,3,F
F,1,D,3,G,2,A
D,2,A,2,B,1,C,2,E,3,G,1,F
Krusal's Algorithm Implementation:
The second line for example (B,1,A,1,C,2,D) means that the B is connected to A with weight 1; B is connected to C with weight 1, and B is connected to D with weight 2.
Start by creating an Edge class that will have node1 (String), node2 (String), and weight (int)
Then, read the text file line by line; for each line, loop through the edges and create an Edge object for each edge. Add that edge to an array of Edges
Sort that array according to their weights; you can use Arrays.sort()
Sorting used in Krusal's Algorithm:
After sorting all the edges, you need loop through them (starting at smallest weight) and for each edge check the root of node1 and node2 (using function "findRoot" that you will have to implement); if the two roots are the same, do not print that edge and go to next edge; if the two roots are different, print the edge (C,1,B for example), make changes to the parent array, and add the weight of that edge (1) to a variable that will contain the weight of the entire minimum spanning tree, and go to next edge.
findRoot function in Krusal's Algorithm:
"findRoot" will check the dictionary (or HashMap) of the nodes and their parents (description in the video)
One thing that you would want to keep in mind is that in your array that contains all edges, you don't want to have the same edge twice; you can use an additional HashMap to check whether that edge already exists of not.
Comments
Post a Comment