Objective: Work with graphs and Kruskals algorithm for minimum spanning trees

Subject:Computer SciencePrice: Bought3

Share With

Objective:

     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 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
//
// CONSTRUCTION: with int representing initial number of sets
//
// ******************PUBLIC OPERATIONS*********************
// void union( root1, root2 ) --> Merge two sets
// int find( x )              --> Return set containing x
// ******************ERRORS********************************
// No error checking is performed

/**
 * Disjoint set class, using union by rank and path compression.
 * Elements in the set are numbered starting at 0.
 * @author Mark Allen Weiss
 */
public class DisjSets
{
    /**
     * Construct the disjoint sets object.
     * @param numElements the initial number of disjoint sets.
     */
    public DisjSets( int numElements )
    {
        s = new int [ numElements ];
        for( int i = 0; i < s.length; i++ )
            s[ i ] = -1;
    }

    /**
     * Union two disjoint sets using the height heuristic.
     * For simplicity, we assume root1 and root2 are distinct
     * and represent set names.
     * @param root1 the root of set 1.
     * @param root2 the root of set 2.
     */
    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
        }
    }

    /**
     * Perform a find with path compression.
     * Error checks omitted again for simplicity.
     * @param x the element being searched for.
     * @return the set containing x.
     */
    public int find( int x )
    {
        if( s[ x ] < 0 )
            return x;
        else
            return s[ x ] = find( s[ x ] );
    }

    private int [ ] s;


    // Test main; all finds on same output line should be identical
    public static void main( String [ ] args )
    {
        int NumElements = 128;
        int NumInSameSet = 16;

        DisjSets ds = new DisjSets( NumElements );
        int set1, set2;

        for( int k = 1; k < NumInSameSet; k *= 2 )
        {
            for( int j = 0; j + k < NumElements; j += 2 * k )
            {
                set1 = ds.find( j );
                set2 = ds.find( j + k );
                ds.union( set1, set2 );
            }
        }

        for( int i = 0; i < NumElements; i++ )
        {
            System.out.print( ds.find( i )+ "*" );
            if( i % NumInSameSet == NumInSameSet - 1 )
                System.out.println( );
        }
        System.out.println( );
    }
}

 

 

ArrayList<Edge> kruskal( List<Edge> edges, int numVertices )

{

DisjSets ds = new DisjSets( numVertices );

PriorityQueue<Edge> pq = new PriorityQueue<>( edges );

List<Edge> 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;

}

 

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