Kruskals algorithm

Overarching idea

Build a subgraph by repeatedly choosing the minimum edge which does not form a cycle.

Steps

  1. Choose a vertex as the initial MST subgraph, S.

  2. Choose the minimum edge which connects S to any other vertex in the graph, G. This vertex should not be connected to S.

  3. Repeat step 2.

Runtime

Runtime - O(n^2)

Use min heap to find minimum edge - O(nlogn) (logn to get minimum edge each time, n - 1 times)

logo