Kruskal Algorithm - Finding Minimum Spanning Tree

Graph

Share

In this tutorial we will learn to find Minimum Spanning Tree (MST) using Kruskal's Algorithm.

Graph

Consider the following graph.


We will find MST for the above graph shown in the image.

Steps

Step 1: Remove all loops

Any edge that starts and ends at the same vertex is a loop.

Loops are marked in the image given below.


Step 2: Remove all parallel edges between two vertex except the one with least weight

In this graph, vertex A and C are connected by two parallel edges having weight 2 and 12 respectively. So, we will remove 12 and keep 2.


We are now ready to find the MST – Minimum Spanning Tree.

Step 3: Create the edge table

An edge table will have name of all the edges along with their weight is ascending order.


Now if you look at the graph, then you will notice that there are total 5 edges. So our edge table will have 5 columns.

Edge BC AB AC DC BD
Weight 1 2 2 3 5

Note! Our graph has 4 vertices so, our MST will have 3 edges.

How we will proceed

To find the MST (Minimum Spanning Tree) we will start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges.

Result


Pseudo Code

/**
 * G = input graph
 * MST = Minimum Spanning Tree graph
 * E = no. of Edges
 * V = no. of Vertices
 *
 * Assumed that G has no loop and no parallel edges
 */

Given: G(E,V)

// sort edges in ascending order by weight
sort(G)

// create MST
Create: MST(V-1, V)	// total edges of MST = V-1, total vertices = V

// find MST
set: j = 0;
set: i = 0;

while (i < E and j < V-1) do
	
	// temporarily add edge[i] of graph G to graph MST
	set: MST->edge[j] = G->edge[i];
	set: MST->E = j + 1;

	// check if graph MST has no cycle after adding the edge[i] of graph G
	if !hasCycle(MST) then

		// we are keeping the edge[i] of G in MST
		set: j = j + 1;

	endif

	set: i = i + 1;

endwhile

display: MST

Code

Note! In the given code we are representing Vertices using decimal numbers.
So,
vertex A is denoted by digit 0.
vertex B is denoted by digit 1.
vertex C is denoted by digit 2.
vertex D is denoted by digit 3.

/**
 * file: kruskal.c
 * author: yusuf shakeel
 * date: 2014-03-01
 *
 * description: find the MST using kruskal algorithm.
 *
 * vertices are numbered from 0.
 * so,
 * vertex A becomes 0
 * vertex B becomes 1
 * and so on...
 */

#include <stdio.h>
#include <stdlib.h>

/**
 * weighted edge of the graph
 */
struct Edge {

	int start;		//starting vertex (node) of the edge
	int end;		//ending vertex (node) of the edge
	int weight;		//weight of the edge

};

/**
 * the graph
 */
struct Graph {

	int E;		//number of edges in the graph
	int V;		//number of vertices in the graph
	struct Edge* edge;	//pointer to array of edges
	
};

/**
 * this is for the subset
 */
struct subset {
	
	int parent;		//this is the parent of the subset
	int rank;		//this is the rank of the subset

};

/**
 * this function will create a graph and will return pointer to the graph
 */
struct Graph* createGraph(int E, int V) {

	//creating graph pointer
	struct Graph* graph = (struct Graph*) malloc (sizeof(struct Graph));
	
	//assign no. of edge and no. of vertex
	graph->E = E;
	graph->V = V;

	//pointer to edge
	graph->edge = (struct Edge*) malloc (graph->E * sizeof(struct Edge));

	//return graph pointer
	return graph;

}

/**
 * this function will find the subset in which
 * the vertex i belongs
 */
int Find(struct subset subsets[], int i) {
	
	if (subsets[i].parent != i) {

		subsets[i].parent = Find(subsets, subsets[i].parent);

	}
	
	return subsets[i].parent;

}

/**
 * this function will perform union operation on two subsets
 */
void Union(struct subset subsets[], int vertXSubset, int vertYSubset) {

	int rootOfX = Find(subsets, vertXSubset);
    int rootOfY = Find(subsets, vertYSubset);
 
    if (subsets[rootOfX].rank < subsets[rootOfY].rank) {
     
        subsets[rootOfX].parent = rootOfY;

    }
    else if (subsets[rootOfX].rank > subsets[rootOfY].rank) {

        subsets[rootOfY].parent = rootOfX;

    }
    else {

        subsets[rootOfY].parent = rootOfX;
        subsets[rootOfX].rank++;

    }
}

/**
 * this function will sort the edges of a graph by weight
 * in ascending order
 */
void sort(struct Graph* graph) {

	//variables
	int i, j, noOfEdges = graph->E;
	struct Edge* tempEdge = (struct Edge*) malloc (sizeof(struct Edge));

	//bubble sort
	//you can use any other sorting of your choice
	for (i = 1; i < noOfEdges; i++) {
		for (j = 0; j < noOfEdges - i; j++) {

			if (graph->edge[j].weight > graph->edge[j+1].weight) {

				tempEdge->start = graph->edge[j].start;
				tempEdge->end = graph->edge[j].end;
				tempEdge->weight = graph->edge[j].weight;

				graph->edge[j] = graph->edge[j+1];

				graph->edge[j+1].start = tempEdge->start;
				graph->edge[j+1].end = tempEdge->end;
				graph->edge[j+1].weight = tempEdge->weight;

			}
		}
	}

}

/**
 * this function will display the MST (minimum spanning tree)
 */
void displayMST(struct Graph* graphMST) {
	int i, noOfEdges = graphMST->E;
	for (i = 0; i < noOfEdges; i++) {
		printf("Edge %d-->%d Weight: %d\n", graphMST->edge[i].start, graphMST->edge[i].end, graphMST->edge[i].weight);
	}
}

/**
 * this function will return 1 if cycle is found
 * in the graph otherwise 0
 */
int hasCycle(struct Graph* graph) {

	//variable
	int i, j, vertXSubset, vertYSubset;

	//total number of vertices in the graph
	int V = graph->V;
	int E = graph->E;

	/**
	 * create subset
	 */
	struct subset* subsets = (struct subset*) malloc (V * sizeof(struct subset));

	//initialize subset
	for (i = 0; i < V; i++) {

		subsets[i].parent = i;
		subsets[i].rank = 0;

	}

	//detect cycle
	for (j = 0; j < E; j++) {

		vertXSubset = Find(subsets, graph->edge[j].start);
		vertYSubset = Find(subsets, graph->edge[j].end);

		if (vertXSubset == vertYSubset) {

			return 1;

		}

		Union(subsets, vertXSubset, vertYSubset);

	}
	

	return 0;

}

/**
 * kruskal function to compute MST
 */
void kruskal(struct Graph* graph) {

	//variables
	int i, j;

	//number of edges and vertices in the graph
	int E = graph->E;
	int V = graph->V;

	/**
	 * sort the edges of the graph in ascending order of weight
	 */
	sort(graph);
	
	/**
	 * MST graph
	 */
	struct Graph* graphMST = createGraph(V - 1, V);

	/**
	 * find MST
	 */
	//now check other edges
	for (i = 0, j = 0; i < E && j < V - 1; i++) {

		graphMST->edge[j] = graph->edge[i];
		graphMST->E = j + 1;

		if (!hasCycle(graphMST)) {

			j++;

		}

	}


	/**
	 * display the computed MST (minimum spanning tree)
	 */
	displayMST(graphMST);

}

/**
 * the main function
 */
int main (void) {

	//total number of edges and vertices
	int E = 5;
	int V = 4;

	/**
	 * create graph
	 */
	struct Graph* graph = createGraph(E, V);

	/**
	 * add edges to the graph
	 */
	//edge: A -- B
	graph->edge[0].start = 0;
	graph->edge[0].end = 1;
	graph->edge[0].weight = 2;
	
	//edge: A -- C
	graph->edge[1].start = 0;
	graph->edge[1].end = 2;
	graph->edge[1].weight = 2;
	
	//edge: B -- C
	graph->edge[2].start = 1;
	graph->edge[2].end = 2;
	graph->edge[2].weight = 1;
	
	//edge: B -- D
	graph->edge[3].start = 1;
	graph->edge[3].end = 3;
	graph->edge[3].weight = 5;
	
	//edge: D -- C
	graph->edge[4].start = 3;
	graph->edge[4].end = 2;
	graph->edge[4].weight = 3;

	/**
	 * find MST using kruskal
	 */
	kruskal(graph);

	return 0;
}

Output

Edge 1-->2 Weight: 1
Edge 0-->1 Weight: 2
Edge 3-->2 Weight: 3