Kruskal's algorithm for extracting Minimum Spanning Tree (MST)

This algorithm comes under the greedy method, which means that the objects are chosen to join a growing collection by iteratively picking an object that minimizes some cost function.

Now, taking account of the above mentioned greedy method, the Kruskal's algorithm with a graph considers the edges in order of their weights to grow the Minimum Spanning Tree (MST) in clusters.

The Kruskal's algorithm can be broken down as follows:
Step 1: In a given undirected graph [G] consider each vertex is in its own cluster all by itself i.e. if a [G] has four vertices then you have four cluster initially
Step 2: Look for each edges in turn, ordered by increasing weight i.e. arrange all the edges in ascending order
Step 3: Start with the smallest weighing edge. If this edge connects two different clusters then it is considered as the min-weight "bridge" edge [e] and added to the set of edges of the MST. In this initial stages, due to addition of [e] to the MST (i.e. the growth of the MST), the two clusters then are merged into a single cluster. However, if a given [e] connects to two vertices that are already in the identified cluster then this [e] is discarded.
Step 4: Now iteratively the algorithm adds enough [e] to a set of edges of spanning tree, it terminates and outputs this tree as the MST.


Pseudo-code of the Kruskal's algorithm
// Kruskal(G) [Time complexity = O(m * log * n)]
// Input: A simple connected weight graph [G] with [n] vertices and [m] edges
// Output: A minimum spanning tree [T] for [G]
for each vertex [v] in [G] do
Define an elementary cluster C(v) <- {v}

// Initialise a priority queue Q to contain all edges in [G], using the weights as keys
T <- null
// The above [T] will ultimately contain the edges of the MST

while [T] has fewer then n-1 edges do
(u,v) <- Q.removeMin()
// Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
if C(v) != C(u) the
Add edges (v,u) to T
Merge C(v) & C(u)
// The above union of C(v) & C(u) yields a single cluster
return tree T

Example below shows the Kruskal's algorithm that extracts the MST from a spanning tree. This spanning tree depicts a subset of Finnish intercity roadways route:

--------------------------------------------
Stage 1.
--------------------------------------------
Main cluster (C) contains the following vertices: null
Elementary Cluster (C1) contains the following vertices: null

Priority Queue (Q)
------------------
----
110
----
137
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {null}
Set of discarded edges d = {null}

--------------------------------------------
Stage 2.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere

Priority Queue (Q)
------------------
----
137
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110}
Set of discarded edges d = {null}

--------------------------------------------
Stage 3.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere
Elementary Cluster (C2) contains the following vertices: Helsinki+Kouvola

Priority Queue (Q)
------------------
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,}
Set of discarded edges d = {null}

--------------------------------------------
Stage 4.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku
Elementary Cluster (C2) contains the following vertices: Helsinki+Kouvola

Priority Queue (Q)
------------------
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141}
Set of discarded edges d = {null}

--------------------------------------------
Stage 5.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola

Priority Queue (Q)
------------------
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,}
Set of discarded edges d = {null}

--------------------------------------------
Stage 6.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola

Priority Queue (Q)
------------------
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,}
Set of discarded edges d = {177,}

--------------------------------------------
Stage 7.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294}
Set of discarded edges d = {177,}

--------------------------------------------
Stage 8.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,}
Set of discarded edges d = {177,381}

--------------------------------------------
Stage 9.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294}
Set of discarded edges d = {177,381,409}

--------------------------------------------
Stage 10.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio+Oulu

Priority Queue (Q)
------------------
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,534,}
Set of discarded edges d = {177,381,409}

--------------------------------------------
Stage 11.
--------------------------------------------
Main cluster (C) contains the following vertices = C1
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio+Oulu+Ivalo

Priority Queue (Q)
------------------
null
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,534,549}
Set of discarded edges d = {177,381,409}