Graph

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

Consider the following graph.

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

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

Loops are marked in the image given below.

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.

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.

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.

```
/**
* 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
```

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;
}
```

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