Minimum Spanning Tree is used to solve many real-life problems. Kruskal's algorithm solves the problem in different approach than Prim's algorithm. In this algorithm, the edges of the graph are sorted in ascending order. Then the edges are chosen for the minimum spanning tree one after another, if selection of the edge does not form any cycle. Thus, during formation of the spanning tree, a forest is formed in intermediate steps. At the end of the algorithm, the trees are combined and one tree is formed.
To implement this algorithm, disjoint set data structure is used. The algorithm begins with a forest, where each vertex of the graph is considered as a component.
The edges are examined in order from lightest to heaviest, an edge is considered as safe if and only if its endpoints are in different components of the forest F. If two end points of an edge belongs to same component, selection of the edge forms a cycle. Hence, the edge is not selected for the spanning tree.
Algorithm
Example
Step-by-step
Complexity Analysis
In our case, the sets are components of F, and n = |V|. Kruskal's algorithm performs O(E) FIND operations, two for each edge in the graph, and O(V) UNION operations, one for each edge in the minimum spanning tree. Using union-by-rank and path compression allows us to perform each UNION or FIND in O(α(E, V)) time, where α is the not-quite-constant inverse-Ackerman function. So ignoring the cost of sorting the edges, the running time of this algorithm is O(E α(E, V)). We need O(E log E) = O(E log V) additional time just to sort the edges. Since this is bigger than the time for the UNION-FIND data structure, the overall running time of Kruskal's algorithm is O(E log V).
Implementation using C Programming Language
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int find(int i, int *parent)
{
while(parent[i])
i = parent[i];
return i;
}
int myunion(int i, int j, int *parent)
{
if(i != j)
{
parent[j] = i;
return 1;
}
return 0;
}
void kruskal(int size, int **adjMat, int *parent, int minCost, int chk){
int min = 0, r = 0, c = 0, i = 0, j = 0;
while(chk <= size){
for(i = 1, min = INT_MAX; i <= size; i++){
for(j = 1; j <= size; j++){
if(min > adjMat[i][j] && adjMat[i][j] != 0){
min = adjMat[i][j];
r = i;
c = j;
}
}
}
if(myunion(find(r, parent),find(c, parent), parent)){
minCost += adjMat[r][c];
}
adjMat[r][c] = adjMat[c][r] = INT_MAX;
chk++;
}
printf("%d", minCost);
}
int main(){
int size, minCost = 0, chk = 1, **adjMat, *parent, i = 0, j = 0;
scanf("%d", &size);
parent = (int *)malloc((size + 1) * sizeof(int));
adjMat = (int **)malloc((size + 1)*sizeof(int *));
for(i = 0; i <= size; i++)
adjMat[i] = (int *)malloc((size + 1) * sizeof(int));
for(i = 0; i <= size; i++)
parent[i] = 0;
for(i = 1; i <= size; i++){
for(j = 1; j <= size; j++){
scanf("%d", &adjMat[i][j]);
if(adjMat[i][j] == 0){
adjMat[i][j] = INT_MAX;
}
}
}
kruskal(size, adjMat, parent, minCost, chk);
return 0;
}
Posts
No comments:
Post a Comment