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

  3. repeat until $V-1$ edges are added

performance analysis