Lab Kruskal - Kruskal's Algorithm

A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. For example, in the 9-node graph shown below, the spanning tree is the subgraph formed by the bold edges.

In an undirected weighted graph, a minimum spanning tree is a spanning tree with the minimum possible total edge weight. Figure 2 shows an undirected graph, one of its spanning trees and the minimum spanning tree. Notice the difference in cost (total edge weight) of the spanning tree vs the minimum spanning tree.

In this lab you will implement Kruskal's algorithm, a well-known algorithm for finding the minimum spanning tree of weighted graphs. The algorithm can be stated as follows:

Given: a weighted undirected graph
Return: the minimum spanning tree
------------------------------------------------------------
A = empty list
S = sorted list of edges in ascending order of weight
For every edge e in S, while there are nodes unconnected:
    if A ⋃ e does not form a cycle:
        A = A ⋃ e

The following is a step by step demonstration of running Kruskal's algorithm on a undirected weighted graph:

	S would consist of (1,2,2), (1,0,4), (0,2,4), (0,3,6), (0,4,6), (2,3,8), (3,4,9), where each triplet (u,v, w) specifies the nodes u, v joined by an edge and the weight w of the edge. A is empty.
	The first edge in the sorted list is (1,2). It is added to A since it does not form a cycle. Now A contains (1,2)
	The edge (1,0) does not form a cycle with the other edges in A.Let's add it to the A.Now A contains (1,2), (1,0)
	The next edge on S is (0,2). If we added it to A it would form a cycle. Thus, we will not add it to S.
	The next edge on S is (0,3). It does not form a cycle with the other edges in A. Let's add it to the A. Now A contains (1,2), (1,0) (0,3)
	The next edge on S is (0,4). It does not form a cycle with the other edges in A. Let's add it to the A. Now A contains (1,2), (1,0) (0,3), (0,4). All the nodes of the original graph are connected by the edges in A. Thus, the algorithm stops. The minimum weight spanning tree is composed of edges (1,2), (1,0) (0,3), (0,4)

The step of checking if an edge that is added to A will form a cycle is critical to the performance of this algorithm. For this lab we will implement this check in a not-so-efficient but easy to understand manner.

We will keep an array B of size |V| where V is the set of nodes and |V| is the number of nodes. Initially, each element B will contain exactly the value of its index. For the 5-node graph above, array B would initially contain:

which represents that, at the beginning, since A is empty, there are no nodes connected, i.e every node is in its own connected component.

As the algorithm progresses, everytime that we link two nodes because we added an edge (u,v) between them to A, we will update B to indicate that they are now in the same component. For example, when we add (1,2) to A, we change every occurrence of 2 in the array to 1. We obtain:

At this point, nodes 1 and 2 are in the same connected component.

When we are about to add the edge (0,1) we must check if it create a cycle. We do this by checking that 0 and 1 do not already belong to the same connected component. This is easily checked: if the content of B[0] != B[1] they are not in the same component. Since they are not, we proceed to add (0,1) to A and update B by changing all the nodes in 1's component to 0's component, i.e. changing the content of B[1] and B[2] to 0.

When we are about to add edge (0,2) we check whether 0 and 2 are in the same group. Turns out that they are in the same group, since B[0] == B[2], so we don't add (0,2) to A and do not modify B.

When considering (0,3), B[0] != B[3]. Thus we add (0,3) to A, and B becomes.

When considering (0,4), B[0] != B[4]. Thus we add (0,4) to A, and B becomes.

Now all the nodes are connected using the edges in A. Therefore the spanning tree is completed.