[prev] [index] [next]

Implementation of Kruskal's Algorithm

C-like description of algorithm:

MSTree kruskalFindMST(Graph g)
{
   Graph mst = newGraph(); //MST initially empty
   Edge eList[g->nV]; //sorted array of edges
   edges(eList, g->nE, g);
   sortEdgeList(eList, g->nE);
   int i;  Edge e;
   for (i = 0; mst->nE < g->nV-1; i++) {
      e = eList[i];
      insertE(mst, e);
      if (hasCycle(mst)) removeE(mst, e);
   }
   return mst;
}