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

1. generate all spanning trees
2. calculate total weight
3. find the minimum

Kruskal’s algorithm

1. start with an empty MST

2. loop through edges in increasing weight order

   • add edge if it does not form a cycle in the MST

3. 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)