[prev] [index] [next]

Kruskal's Algorithm

One approach to computing MST for graph G(V,E): 

MSTree KruskalMST(Graph g)
{
   MST = empty graph (nV(g))
   sortedEdgeList = sort edges(g) by weight
   foreach (edge e in sortedEdgeList) {
      add e to MST
      if (MST has a cyle) remove e from MST
      if (MST has nV(g) vertices) break
   }
   return MST
}

Critical operations:  sorting edges O(ElogE),  checking for cycles O(EV)


Reminder: MST = subgraph, with all vertices, and minimum sum-of-edge-weights