# Kruskals algorithm

### Overarching idea

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

### Steps

Choose a vertex as the initial MST subgraph, S.

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

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)