C Program To Implement Kruskal’s Algorithm For Minimum Spanning Tree
Learn How To Create a Minimum Spanning Tree using Kruskal’s Algorithm in C Programming Language. Kruskal’s Algorithm is a Greedy Algorithm approach that works best by taking the nearest optimum solution.
What is Minimum Spanning Tree?
A Spanning Tree of any graph G whose sum of the weights is minimum amongst all the spanning trees of G, is called the Minimum Spanning Tree of the graph G.
What is Kruskal’s Algorithm?
Kruskal’s algorithm is a minimum spanning tree algorithm to find an Edge of the least possible weight that connects any two trees in a given forest. Initially, a forest of n different trees for n vertices of the graph are considered. Each tee is a single vertex tree and it does not possess any edges. In every iteration, an edge is considered and it is included in the spanning tree if it does not form a cycle. If it forms a cycle, then it is not included.
Steps for Kruskal’s Algorithm
- Sort all the Edges in the increasing order
- Find the Edge with the minimum weight
- Include it if it does not form a cycle
- Repeat the above steps till v – 1 Edges where v is the total number of vertices
The Kruskals Algorithm is faster than Prim’s Algorithm as in Prim’s Algorithm, an Edge may be considered more than once whereas in Kruskal’s Algorithm, an Edge is considered only once.
Must Read: C Program To Implement Prim’s Algorithm
C Program To Implement Kruskal’s Algorithm to Find Minimum Spanning Tree
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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | #include<stdlib.h> #include<stdio.h> #define NIL -1 #define MAX 100 struct edge { int x; int y; int weight; struct edge *link; }*front = NULL; void create_tree(struct edge tree[]); void insert_queue(int i, int j, int wt); struct edge *delete_queue(); int isEmpty(); void make_a_graph(); int vertices; int main() { int count; struct edge tree[MAX]; int tree_weight = 0; make_a_graph(); create_tree(tree); printf("Edges in MST:\n"); for(count = 1; count <= vertices - 1; count++) { printf("%d->", tree[count].x); printf("%d\n", tree[count].y); tree_weight = tree_weight + tree[count].weight; } printf("Total Weight of this Minimum Spanning Tree:\t%d\n", tree_weight); return 0; } void create_tree(struct edge tree[]) { struct edge *tmp; int y1, y2, root_y1, root_y2; int parent[MAX]; int i, count = 0; for(i = 0; i < vertices; i++) { parent[i] = NIL; } while(!isEmpty( ) && count < vertices - 1) { tmp = delete_queue(); y1 = tmp->x; y2 = tmp->y; while(y1 != NIL) { root_y1 = y1; y1 = parent[y1]; } while(y2 != NIL) { root_y2 = y2; y2 = parent[y2]; } if(root_y1 != root_y2) { count++; tree[count].x = tmp->x; tree[count].y = tmp->y; tree[count].weight = tmp->weight; parent[root_y2] = root_y1; } } if(count < vertices - 1) { printf("Graph is Disconnected. Therefore, Spanning Tree is not possible\n"); exit(1); } } void insert_queue(int i, int j, int wt) { struct edge *tmp, *q; tmp = (struct edge *)malloc(sizeof(struct edge)); tmp->x = i; tmp->y = j; tmp->weight = wt; if(front == NULL || tmp->weight < front->weight) { tmp->link = front; front = tmp; } else { q = front; while(q->link != NULL && q->link->weight <= tmp->weight) { q = q->link; } tmp->link = q->link; q->link = tmp; if(q->link == NULL) { tmp->link = NULL; } } } struct edge *delete_queue() { struct edge *tmp; tmp = front; front = front->link; return tmp; } int isEmpty() { if(front == NULL) { return 1; } else { return 0; } } void make_a_graph() { int count, weight, maximum_edges, origin_vertex, destination_vertex; printf("Enter Total Number of Vertices:\t"); scanf("%d", &vertices); maximum_edges = vertices * (vertices - 1)/2; for(count = 0; count < maximum_edges; count++) { printf("Enter Edge [%d] Co-ordinates [-1 -1] to Quit\n", count + 1); printf("Enter Origin Point:\t"); scanf("%d", &origin_vertex); printf("Enter Destination Point:\t"); scanf("%d", &destination_vertex); if((origin_vertex == -1) && (destination_vertex == -1)) { break; } printf("Enter Weight for this Edge:\n"); scanf("%d", &weight); if(origin_vertex >= vertices || destination_vertex >= vertices || origin_vertex < 0 || destination_vertex < 0) { printf("Entered Edge Co - ordinates is Invalid\n"); count--; } else { insert_queue(origin_vertex, destination_vertex, weight); } } } |
Must Read: C Program To Implement Warshall’s Algorithm
Output
In case you get any Compilation Errors or any doubts in this Code To Make Minimum Spanning Tree using Kruskal’s Algorithm in C Programming, let us know about it in the Comment Section below. Check this article on GeeksforGeeks for more information on Kruskals Algorithm.
A Minimum Spanning Tree is an application of a Disjoint Data Structure.