Use Java

Name: Kruskals.jaObjective:

 Work with graphs and Kruskals algorithm for minimum spanning trees. Overview: The pseudocode for Kruskals algorithm is given in the textbook to find a minimum spanning tree of a graph. Your program will find the minimum spanning tree among a set of cities in Texas. Details: Write a command-line program that uses Kruskal's algorithm to find a minimum spanning tree of a graph. The graph will be provided as a file named assn9_data.csv. The data in the file is in the form of an adjacency list. You must use the author's DisjSets class without modifying it. You can either use one of the author's priority queue classes or you can use the PriorityQueue class provided in Java. You should output each edge of your minimum spanning tree as the names of the two cities and the distance between them. You should also print the sum of all of the distances in the tree.  

DisjSets Class provided in the book:

public class DisjSets { public DisjSets(int numElements)

{

s = new int[numElements];

for (int i = 0; i < s.length; i++)

s[i] = -1;

}

public void union(int root1, int root2)

{

if (s[root2] < s[root1]) // root2 is deeper

s[root1] = root2; // Make root2 new root

else

{

if (s[root1] == s[root2])

s[root1]--; // Update height if same

s[root2] = root1; // Make root1 new root

}

}

public int find(int x)

{

if (s[x] < 0)

return x;

else

return find(s[x]);

}

private int[] s;

}

assn9_data.csv contents 

:

Abilene,Dallas,184,San Angelo,90,Waco,184,Wichita Falls,142 Amarillo,El Paso,440,Lubbock,123,Wichita Falls,225 Austin,Bryan,103,Killeen,68,San Antonio,80 Brownsville,Corpus Christi,161,McAllen,60 Bryan,Austin,103,Houston,100,Tyler,146,Waco,86 Corpus Christi,Brownsville,161,Houston,217,Laredo,143,McAllen,154,San Antonio,143 Dallas,Abilene,184,Longview,126,Texarkana,177,Tyler,95,Wichita Falls,142 El Paso,Amarillo,440,Laredo,606,Midland,305 Houston,Bryan,100,Corpus Christi,217,San Antonio,197,Tyler,199 Killeen,Austin,68,San Angelo,184,Waco,63 Laredo,Corpus Christi,143,El Paso,606,McAllen,144,Midland,418,San Antonio,156 Longview,Dallas,126,Texarkana,90,Tyler,38 Lubbock,Amarillo,123,Midland,118,Wichita Falls,210 McAllen,Brownsville,60,Corpus Christi,154,Laredo,144 Midland,El Paso,305,Laredo,418,Lubbock,118,San Angelo,112 San Angelo,Abilene,90,Killeen,184,Midland,112,San Antonio,212,Waco,215,Wichita Falls,239 San Antonio,Austin,80,Corpus Christi,143,Houston,197,Laredo,156,San Angelo,212 Texarkana,Dallas,177,Longview,90,Wichita Falls,272 Tyler,Bryan,146,Dallas,95,Houston,199,Longview,38,Waco,132 Waco,Abilene,184,Bryan,86,Killeen,63,San Angelo,215,Tyler,132 Wichita Falls,Abilene,142,Amarillo,225,Dallas,142,Lubbock,210,San Angelo,239,Texarkana,272 

Psuedocode Kruskal's algorithm:

ArrayList kruskal( List edges, int numVertices )

{

DisjSets ds = new DisjSets( numVertices );

PriorityQueue pq = new PriorityQueue<>( edges );

List mst = new ArrayList<>( );

while( mst.size( ) != numVertices - 1 )

{

Edge e = pq.deleteMin( ); // Edge e = (u, v)

SetType uset = ds.find( e.getu( ) );

SetType vset = ds.find( e.getv( ) );

if( uset != vset )

{

// Accept the edge

mst.add( e );

ds.union( uset, vset );

}

}

return mst;

}