Minimum Spanning Tree using kruskal algorithm
Here you will learn the program code to find minimum spanning tree using kruskal algorithm in C programming.
What is minimum spanning tree?
A minimum spanning tree is a subset of edges from a connected graph that connects all its vertices with the minimum possible total edge weight, forming a tree-like structure.
Spanning Tree Calculation
C program to find minimum spanning tree using kruskal algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 10 int cost[MAX][MAX], n, dis[MAX], visited[MAX], flag[MAX][MAX], path[MAX]; int mincost = 0, min; int find(int); int union1(int, int); void Fun_kruskal(); int main() { int i, j; printf("\nInput number of vertices : "); scanf("%d", &n); printf("\nInput cost adjacency matrix : \n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", &cost[i][j]); if (cost[i][j] == 0) cost[i][j] = 999; } } Fun_kruskal(); printf("\nMinimum cost is : %d\n", mincost); printf("\n\nEdges in MST are : \n"); for (i = 0; i < n; i++) if (path[i] != -1) printf("\n%d -> %d", i, path[i]); return 0; } void Fun_kruskal() { int i, j, u, v, num = 1; mincost = 0; while (num < n) { for (i = 0, min = 999; i < n; i++) { for (j = 0; j < n; j++) { if (cost[i][j] < min) { min = cost[i][j]; u = i; v = j; } } } if (find(u) != find(v)) { union1(u, v); printf("\nEdge %d\t(%d -> %d)\tcost : %d", num++, u, v, min); mincost = mincost + min; path[u] = v; } cost[u][v] = cost[v][u] = 999; } } int find(int i) { while (visited[i] != 0) i = visited[i]; return i; } int union1(int i, int j) { if (i != j) { visited[j] = i; return 1; } return 0; } |
Output
Input number of vertices : 3
Input cost adjacency matrix :
1
2
3
4
5
6
7
8
9
Edge 1 (0 -> 1) cost : 2
Edge 2 (0 -> 2) cost : 3
Minimum cost is : 5
Edges in MST are :
0 -> 2
1 -> 0
2 -> 0
Read Also
Implement N Queens Problem using Backtracking
1/2 Knapsack Problem Using Dynamic Programming in C
Knapsack Problem Using Greedy Solution