[prev] 27 [next]

Kruskal's Algorithm

One approach to computing MST for graph G(V,E):
  • start with empty MST
  • consider edges in increasing weight order
  • add edge if it does not form a cycle in MST
  • repeat until V-1 edges are addedw
Critical operations:
  • iterating over edges in weight order
  • checking for cycles in a graph