MinSpanTree(G) uses Kruskals Algorithm to find and return the edges of the minimum spanning tree of graph G.

typedef struct {

Vertex v; Vertex w; int weight;

} Edge;

Edge *MinSpanTree( Graph G )

{ Edge e, *GraphEdges, *TreeEdges;

DisjSet S;

PriorityQueue H;

SetType w_set, v_set;

N = NumOfVex( G );

S = CreateDisjSet( N ); /* create disjoint set S */

GraphEdges = GetEdges(G); /* get all edges of graph G */

TreeEdges = malloc( sizeof(Edge) * N );

H = BuildHeap( GraphEdges, N ); /* build min heap H from the edges of graph G */

edges_accepted = 0;

while (edges_accepted < N-1 ) {

if (IsEmpty( H )) {

free( TreeEdges );

TreeEdges = NULL;

break;

}

e = ______(1)______;

v_set = ______(2)______;

w_set = ______(3)______;

if( w_set != v_set ) {

TreeEdges[edges_accepted++] = e;

________(4)_______;

}

}

free( GraphEdges );

DestroyHeap( H );

DestroyDisjSet( S );

return TreeEdges;

}