In this article I show you the implementation of Kruskal’s Algorithm using C and C++ Programming Languages. This a popular computer science algorithm which is directly based on the generic Minimum Spanning Tree (MST) algorithm. A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights.
Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
Table of Contents
- Key Concepts
- Kruskal’s Algorithm Steps
- Pseudo code of the Kruskal’s Algorithm
- Complexity of Kruskal’s Algorithm
- C Programming Implementation of Kruskal’s Algorithm
- C++ Programming Implementation of Kruskal’s Algorithm
Key Concepts
- Graph: A collection of vertices (or nodes) and edges connecting pairs of vertices.
- Weighted Graph: A graph where each edge has a numerical value (weight) associated with it.
- Minimum Spanning Tree (MST): A spanning tree of a graph whose total weight is minimized.
Kruskal’s algorithm addresses two problems as mentioned below.
- PROBLEM 1. Give a practical method for constructing a spanning subtree of minimum length.
- PROBLEM 2. Give a practical method for constructing an unbranched spanning subtree of minimum length.
Kruskal’s algorithm is most suitable for sparse graphs (low number of edges). This algorithm is practically used in many fields such as Traveling Salesman Problem, Creating Mazes and Computer Networks etc. It is also helpful in cluster analysis in machine learning as well as geographical mapping.
This algorithm initially appeared in “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem” research paper by Joseph B. Kruskal, Jr. in the proceedings of the American Mathematical Society Vol. 7, No. 1 (Feb., 1956), pp. 48-50.
Kruskal’s Algorithm Steps
- Sort all the edges in the graph in non-decreasing order of their weight.
- Initialize a forest (a set of trees), where each vertex in the graph is a separate tree.
- Initialize an empty set for the MST.
- Process each edge in the sorted order:
- Check if the current edge forms a cycle with the spanning tree formed so far.
- If it does not form a cycle, include this edge in the MST.
- If it forms a cycle, discard the edge.
- Repeat until there are V−1V−1 edges in the MST (where VV is the number of vertices in the graph).
Pseudo code of the Kruskal’s 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 | Kruskal(graph): sort all edges in graph by their weight in non-decreasing order create an empty set for the MST initialize a Union-Find structure for each edge (u, v) in sorted order: if find(u) != find(v): add edge (u, v) to the MST union(u, v) if MST has V-1 edges: break return MST find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] union(x, y): rootX = find(x) rootY = find(y) if rootX != rootY: if rank[rootX] > rank[rootY]: parent[rootY] = rootX else if rank[rootX] < rank[rootY]: parent[rootX] = rootY else: parent[rootY] = rootX rank[rootX] += 1 |
Complexity of Kruskal’s Algorithm
Time Complexity: The time complexity Of Kruskal’s Algorithm is: O(ElogE+ElogV) where E is number of edges and V is the number of vertices. Sorting the edges takes 0(ElogE)O(ElogE) and the union-find operations take 0(ElogV)O(ElogV).
Space Complexity: 0(V+E)O(V+E), due to the storage required for the graph representation and the Union-Find data structure.
Explanation:
Kruskal’s algorithm takes o(e log e) time in sorting of the edges. Here e is numbers of edges and v is the number of vertices in the graph. Further, it iterates all edges and runs a subroutine to find the cycles in the graph which is called union-find algorithm. The union-find algorithm requires o(log v) time and is applied after sorting of edges is completed.
So, Overall Kruskal’s algorithm requires o(e log v) time to run.
C Programming Implementation of Kruskal’s Algorithm
Here is the C program that implements this 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 | #include <stdio.h> #include <conio.h> #include <stdlib.h> int i, j, k, a, b, u, v, n, ne = 1; int min, mincost = 0, cost[9][9], parent[9]; int find(int); int uni(int, int); void main() { printf("\n\tImplementation of Kruskal's Algorithm\n"); printf("\nEnter the no. of vertices:"); scanf("%d", & n); printf("\nEnter the cost adjacency matrix:\n"); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { scanf("%d", & cost[i][j]); if (cost[i][j] == 0) cost[i][j] = 999; } } printf("The edges of Minimum Cost Spanning Tree are\n"); while (ne < n) { for (i = 1, min = 999; i <= n; i++) { for (j = 1; j <= n; j++) { if (cost[i][j] < min) { min = cost[i][j]; a = u = i; b = v = j; } } } u = find(u); v = find(v); if (uni(u, v)) { printf("%d edge (%d,%d) =%d\n", ne++, a, b, min); mincost += min; } cost[a][b] = cost[b][a] = 999; } printf("\n\tMinimum cost = %d\n", mincost); getch(); } int find(int i) { while (parent[i]) i = parent[i]; return i; } int uni(int i, int j) { if (i != j) { parent[j] = i; return 1; } return 0; } |
Output of the C Program
Implementation of Kruskal’s Algorithm
Enter the no. of vertices:3
Enter the cost adjacency matrix:
9
8
7
6
5
4
3
2
3
The edges of Minimum Cost Spanning Tree are
1 edge (3,2) =2
2 edge (3,1) =3
Minimum cost = 5
C++ Programming Implementation of Kruskal’s 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 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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; // Define a structure to represent an edge struct Edge { int src, dest, weight; }; // Define a structure to represent a graph class Graph { public: int V, E; // Number of vertices and edges vector<Edge> edges; // Collection of all edges Graph(int V, int E); void addEdge(int src, int dest, int weight); }; // Constructor Graph::Graph(int V, int E) { this->V = V; this->E = E; } // Function to add an edge to the graph void Graph::addEdge(int src, int dest, int weight) { edges.push_back({src, dest, weight}); } // Find set of an element i (uses path compression technique) int find(vector<int>& parent, int i) { if (parent[i] != i) parent[i] = find(parent, parent[i]); return parent[i]; } // Do union of two sets (uses union by rank) void Union(vector<int>& parent, vector<int>& rank, int x, int y) { int rootX = find(parent, x); int rootY = find(parent, y); if (rootX != rootY) { if (rank[rootX] > rank[rootY]) parent[rootY] = rootX; else if (rank[rootX] < rank[rootY]) parent[rootX] = rootY; else { parent[rootY] = rootX; rank[rootX]++; } } } // Compare two edges according to their weights bool compare(Edge a, Edge b) { return a.weight < b.weight; } // Function to perform Kruskal's algorithm void KruskalMST(Graph& graph) { int V = graph.V; vector<Edge> result; // Store the resultant MST int e = 0; // An index variable for result[] // Step 1: Sort all the edges in non-decreasing order of their weight sort(graph.edges.begin(), graph.edges.end(), compare); // Allocate memory for creating V subsets vector<int> parent(V); vector<int> rank(V, 0); // Create V single-item sets for (int v = 0; v < V; ++v) parent[v] = v; // Number of edges to be taken is equal to V-1 for (auto edge : graph.edges) { if (e >= V - 1) break; int u = find(parent, edge.src); int v = find(parent, edge.dest); // If including this edge does not cause cycle, include it in result if (u != v) { result.push_back(edge); Union(parent, rank, u, v); e++; } } // Print the contents of result[] to display the built MST cout << "Following are the edges in the constructed MST:\n"; for (auto edge : result) cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl; } int main() { int V = 7; // Number of vertices int E = 11; // Number of edges Graph graph(V, E); // Add edges to the graph graph.addEdge(0, 1, 7); graph.addEdge(0, 3, 5); graph.addEdge(1, 2, 8); graph.addEdge(1, 3, 9); graph.addEdge(1, 4, 7); graph.addEdge(2, 4, 5); graph.addEdge(3, 4, 15); graph.addEdge(3, 5, 6); graph.addEdge(4, 5, 8); graph.addEdge(4, 6, 9); graph.addEdge(5, 6, 11); // Perform Kruskal's algorithm KruskalMST(graph); return 0; } |
You can also view implementation of sorting algorithms in C here: Shell Sort, Quick Sort, Insertion Sort, Selection Sort
