spanning tree ST of a graph G
contains all vertices, no cycles, is a connected subgraph of G
minimum spanning tree MST of a graph G
a spanning tree with the minimum possible sum of edge weights
solutions — finding a MST
brute force solution
- generate all spanning trees
- calculate total weight
- find the minimum
Kruskal’s algorithm
-
start with an empty MST
-
loop through edges in increasing weight order
- add edge if it does not form a cycle in the MST
-
repeat until $V-1$ edges are added
- Kruskal’s algorithm pseudocode
performance analysis
- sorting edges ⇒ O(E log E) (depends on sorting algorithm, could be O(E^2))
- iteration through all the edges ⇒ O(V)
- check for cycles ⇒ O(V^2) — if DFS used for cycle checking; or O(V) because we only need to check for cycles around a node from the last-added edge
- cycle checking — using disjoint sets O(V) (a.k.a. a union-find data structure)