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
|