[prev] 42 [next]

Kruskal's Algorithm

One approach to computing MST for graph G with V nodes:

  1. start with empty MST
  2. consider edges in increasing weight order
    • add edge if it does not form a cycle in MST
  3. repeat until V-1 edges are added

Critical operations:

  • iterating over edges in weight order
  • checking for cycles in a graph