Spanning tree of a graph is a connected subgraph with no cycles (acyclic) that includes all the vertices.
A Minimum Spanning Tree (MST) of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of the edges) is no larger than the weight of any other spanning tree.
Hence, a MST is a spanning tree that is:
- Includes all the vertices
A cut in a graph is a partition of its vertices into two (non-empty) sets.
A crossing edge connects a vertex in one set with a vertex in the other.
- Start with all edges in graph colored grey
- Find cut with no black crossing edges, color its min-weight edge black
- Repeat until V-1 edges are colored black
Consider edges in ascending order of weight (priority queue - min heap of edges by weight)
Add next edge to tree T unless doing so creates a cycle
- Check with union find
- If we are connecting two vertices in the same set (component), we will obtain a cycle
V-1edges are attained
The overall time complexity for Kruskal's MST algorithm is
Elog(E) in worst case. As shown in the table below, the dominating factor is
log(E) which gives rise to the complexity.
The time complexity of
Elog(E) can be represented as
Elog(V) since number of edges is at most
V^2 and hence,
log(E) = log(V^2) = 2log(V).
E at most
- Imagine a adjacency matrix. At most, every cell is filled, which is
|Operation||Frequency||Time per Operation|
log**(V) arises due to amortised bound using weight quick union with path compression
As per the table, we can see that the time complexity is dominated by
E*log(E) times of