Kruskal's algorithm in C is a simple and efficient method for identifying a graph's Minimum Spanning Tree (MST). The MST is a set of edges that connects all vertices with the least total weight while avoiding cycles. The algorithm works by sorting all edges by weight and adding them one by one to the MST as long as no cycles are formed. It uses the Union-Find data structure to keep track of connected components.
Reading Time: 8 minutes
Published: April 10, 2025
Kruskal's approach is a well-known method in graph theory for determining the Minimum Spanning Tree (MST) of an undirected, connected graph.
The MST is a subset of the edges that connect each vertex without any cycles and has the minimum overall edge weight. To create the MST, the Kruskal Algorithm always chooses the next smallest edge that doesn't form a cycle.
A greedy algorithm makes decisions step by step, always choosing the best immediate option without looking ahead. This approach is useful and efficient because it doesn't require complex backtracking or recalculations. It's crucial to understand that greedy algorithms only work for problems where a series of local best choices leads to a globally optimal solution.
Greedy algorithms are used in:
Kruskal's algorithm is classified as greedy because it always picks the shortest available edge. Through this, each step is the best decision based on current conditions. It does not reconsider previous choices, which makes it a purely forward-thinking approach. Since the algorithm does not go back and revise its choices, it fits the greedy strategy. Despite this simplicity, Kruskal's algorithm always guarantees the best possible MST.
At each step, the algorithm does the following:
A spanning tree is a subgraph of a connected graph that includes all its vertices but has no cycles. It is called a tree because it follows tree properties:
To understand trees, consider a network of cities connected by roads. A spanning tree would be a way to connect all cities with the minimum number of roads so that you can reach every city without going in loops. Spanning trees are applied in network routing, electrical circuits, and designing efficient transportation paths.
A Minimum Spanning Tree (MST) is a spanning tree that has the least possible total edge weight. Among all possible spanning trees of a graph, the MST has the lowest cost.
For example, in a telecommunication network, an MST can determine the most cost-effective way to connect cities with fiber optic cables, minimizing expenses while maintaining connectivity. Kruskal's algorithm is a highly effective way to find an MST because it processes edges in increasing order and only adds edges that do not form cycles.
The Union-Find algorithm is a key part of Kruskal's algorithm. It is used to check if adding an edge creates a cycle. It maintains a collection of disjoint sets where each set represents a group of connected vertices.
It consists of two main operations:
1. Find: Determines which set a vertex belongs to. If two vertices belong to the same set, they are already connected.
2. Union: Merges two sets when a new edge is added to the MST.
To make these operations fast, path compression and union by rank are used:
Path compression: Speeds up the Find operation by making all nodes in a set point directly to the root.
Union by rank: Ensures that smaller trees are attached under larger trees, keeping the structure balanced.
Kruskal's algorithm is a greedy method for determining a linked, undirected graph's minimum spanning tree (MST). The MST is a subgraph that, without creating any cycles, joins all of the vertices with the lowest possible total edge weight.
Consider a graph with 5 vertices and 6 edges with given edge weights.
In Kruskal's algorithm, a cost table or adjacency matrix with weights is used to represent the edge weights between vertices in a graph. It provides a clear view of the cost of traveling between nodes. It is necessary in sorting edges before selecting them for the Minimum Spanning Tree (MST). By arranging edges in increasing order of weight, Kruskal's algorithm builds the MST while avoiding cycles.
In the table:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 5 | - | 1 | - |
| B | 5 | 0 | 3 | - | 8 |
| C | - | 3 | 0 | 7 | 4 |
| D | 1 | - | 7 | 9 | - |
| E | - | 8 | 4 | - | 0 |
Step 1: Arrange edges according to weight
Sort all the edges from low weight to high.
Step 2: Set the MST's initial state to empty
Start with an empty MST.
Step 3: Give the tree edges
Select the edge with the lowest weight and add the smallest edge to the MST. The Union-Find data structure is used to check this.
Step 4: Make sure the selected edge does not create a cycle
Check whether the current edge and the spanning tree that has been created thus far constitute a cycle. Get rid of the edge if it creates a cycle.
Step 5: Continue until the tree is finished
Keep adding edges in this way until the MST has precisely V-1 edges, where V is the graph's vertex count.
The algorithm stops when the MST has V−1 edges, where "V" is the number of vertices in the graph. If all vertices are connected before reaching V−1 edges, the remaining edges are not needed.
For the given graph above, many spanning trees exist, but there is only one minimum spanning tree. Here is how it is found:
The smallest edge in the graph is A → D (1), so we add it first. At this point, only A and D are connected.
The next smallest edge is B → C (3). Since this does not form a cycle with A-D, we include it. Now, we have two separate trees. These are two disconnected components.
Next, we add C → E (4), as it is the next smallest edge. Now, A-D is still separate, while B-C-E is forming a partial MST.
Now, we add A → B (5), which connects the two separate parts into one structure. At this point, we have a single connected structure.
Now that all vertices (A, B, C, D, E) are connected, the Minimum Spanning Tree (MST) is complete. The remaining edges CD (7) and BE (8) are NOT included, as they would either create a cycle or are too heavy.
For the graph example above, let's look at the implementation of Kruskal algorithm in C.
#include <stdio.h>
#define MAX 5 // Number of vertices
#define EDGES 6 // Number of edges
// Structure to represent an edge
typedef struct {
char src, dest;
int weight;
} Edge;
// Structure to represent the disjoint set
typedef struct {
char parent;
int rank;
} Subset;
// Function prototypes
int find(Subset subsets[], char i);
void unionSet(Subset subsets[], char x, char y);
void kruskal(Edge edges[]);
// Main function
int main() {
Edge edges[EDGES] = {
{'A', 'B', 5},
{'B', 'C', 3},
{'C', 'E', 4},
{'A', 'D', 1},
{'D', 'C', 7},
{'B', 'E', 8}
};
printf("Edges in the Minimum Spanning Tree:\n");
kruskal(edges);
return 0;
}
// Function to find the parent of a vertex in the disjoint set
int find(Subset subsets[], char i) {
if (subsets[i - 'A'].parent != i)
subsets[i - 'A'].parent = find(subsets, subsets[i - 'A'].parent);
return subsets[i - 'A'].parent;
}
// Function to perform union of two sets
void unionSet(Subset subsets[], char x, char y) {
int rootX = find(subsets, x);
int rootY = find(subsets, y);
if (rootX != rootY) {
if (subsets[rootX - 'A'].rank > subsets[rootY - 'A'].rank)
subsets[rootY - 'A'].parent = rootX;
else if (subsets[rootX - 'A'].rank < subsets[rootY - 'A'].rank)
subsets[rootX - 'A'].parent = rootY;
else {
subsets[rootY - 'A'].parent = rootX;
subsets[rootX - 'A'].rank++;
}
}
}
// Function to implement Kruskal's Algorithm
void kruskal(Edge edges[]) {
Edge result[MAX - 1]; // Store the MST
int e = 0; // Count of edges in MST
int i = 0; // Index for sorted edges
// Sort edges by weight using simple bubble sort
for (int j = 0; j < EDGES - 1; j++) {
for (int k = 0; k < EDGES - j - 1; k++) {
if (edges[k].weight > edges[k + 1].weight) {
Edge temp = edges[k];
edges[k] = edges[k + 1];
edges[k + 1] = temp;
}
}
}
// Initialize subsets (disjoint set)
Subset subsets[MAX];
for (int v = 0; v < MAX; v++) {
subsets[v].parent = 'A' + v;
subsets[v].rank = 0;
}
// Process each edge and add to MST if it doesn't form a cycle
while (e < MAX - 1 && i < EDGES) {
Edge nextEdge = edges[i++];
int root1 = find(subsets, nextEdge.src);
int root2 = find(subsets, nextEdge.dest);
if (root1 != root2) { // If cycle is not formed
result[e++] = nextEdge;
unionSet(subsets, root1, root2);
}
}
// Print the result
for (i = 0; i < e; i++)
printf("%c -- %d -- %c\n", result[i].src, result[i].weight, result[i].dest);
}
Edges in the Minimum Spanning Tree:
A -- 1 -- D
B -- 3 -- C
C -- 4 -- E
A -- 5 -- B
=== Code Execution Successful ===
1. Graph Representation: The graph is represented as an array of edges, each containing a source (src), destination (dest), and weight (weight).
2. Sorting Edges: The edges are sorted in ascending order of weight using Bubble Sort.
3. Union-Find Data Structure: The find() function uses path compression to determine the root of a vertex. The unionSet() function merges two sets using union by rank.
4. Building the MST: Edges are added one by one from the sorted list. An edge is added only if it doesn't form a cycle. The process continues until the MST contains (V-1) edges.
5. Final Output: The selected edges form the Minimum Spanning Tree (MST) with the minimum weight possible.
Time Complexity: O(ELogE + ELog V) since it involves sorting edges and union find operations.
Space Complexity: O(V+E) for storing edges and union find subsets.
Prim's algorithm is another method to find the Minimum Spanning Tree (MST) of a graph. Unlike Kruskal's algorithm which works by selecting the smallest edges, Prim's algorithm starts from any vertex and grows the MST one vertex at a time. It always picks the smallest edge that connects to the existing tree.
It uses a priority queue (Min-Heap) for efficiency and works best on dense graphs, which are basically graphs with many edges. The time complexity is O(E log V), where E is the number of edges and V is the number of vertices.
Here are some of the differences between the two:
| Kruskal's Algorithm | Prim's Algorithm |
|---|---|
| Greedy, adds the smallest edge | Greedy, expands from a vertex |
| It uses Union-Find | It uses Min-Heap (Priority Queue) |
| Works best with sparse graphs | Works best with dense graphs |
| O(E log E) complexity | O(E log V) complexity |
| Sorts edges & picks smallest non-cyclic edge | Starts from a vertex & adds smallest connecting edge |
While the algorithm is great to find the least costly route, it also has its downsides. Let's look at some of its pros and cons:
Effective for Sparse Graphs: Kruskal's approach works incredibly effectively on graphs with a sparse edge count, which is significantly lower than the vertex count. The sorting step, which is O(E log E), dominates the algorithm's temporal complexity because it focuses on sorting edges and processing them in order of weight, where E is the number of edges. This temporal complexity is still efficient and controllable in graphs with fewer edges.
Simple to Implement: Kruskal's algorithm is simple to comprehend and use. The procedures involved are sorting edges, iterating through them, and managing the associated components via a disjoint-set data structure. Because the procedure is simple, it's an excellent option for circumstances where simplicity is valued.
Works Well with Edge-List Representation: Kruskal's technique fits in perfectly when graphs are represented as edge lists. When the graph is represented in edge-list form, it is efficient because it processes edges directly without having to go through neighbouring vertices or edges.
Good for Edge-Centric Problems: Kruskal's algorithm works well when the challenge necessitates concentrating on edges, such as in network routing or road construction, where individual connections are essential. Its goal is to minimise the overall weight while gradually choosing edges.
Slower for Dense Graphs: When the number of edges in a thick graph approaches the maximum, Kruskal's algorithm may operate more slowly. In thick graphs, the number of edges E can reach O(V²) (where V is the number of vertices), and the sorting of edges dominates the time complexity. In certain situations, Kruskal's time complexity could be significantly more than Prim's approach.
Requires Efficient Union-Find: Although Kruskal's straightforward approach relies on an effective Union-find data structure to avoid loops. To guarantee performance, the union and find operations need to be optimised using strategies like union by rank and path compression. For big graphs, the algorithm could become inefficient without these optimisations.
Inefficient for Graphs with Many Vertices: When compared to algorithms like Prim's, which operate progressively on the graph's vertices rather than edges, Kruskal's approach may still need a substantial amount of sorting for graphs with a large number of vertices and few edges, resulting in inefficiencies.
Memory Usage: The complete edge list must be kept in memory for Kruskal's approach to work. Because the edge list will need a lot of storage, this could be an issue for very big graphs, particularly if the graph is thick.
The algorithm has plenty of applications in:
Kruskal's algorithm is used to design efficient networks like telephone lines, internet cables, and power grids. It helps connect all points using the shortest possible total distance, which can reduce cost.
In data mining, the algorithm is used to group similar data points together, particularly in hierarchical clustering. This helps in analyzing patterns and finding connections in large data sets.
Images can be treated like graphs, where each pixel is a node. Kruskal's algorithm helps group similar regions, which is useful in tasks like face detection or medical image analysis.
It helps in planning the best paths for transportation systems like roads, railways, or delivery routes. This makes travel more cost-effective.
In databases, Kruskal's algorithm helps remove unnecessary links and makes data retrieval faster. It's also used to improve performance in distributed systems.
Kruskal's algorithm is a strong and effective technique for determining a graph's Minimum Spanning Tree (MST), which works particularly well for sparse graphs with a small number of edges. Its greedy strategy, which uses a disjoint-set data structure to avoid cycles and choose edges in ascending order of weight, guarantees an ideal solution with a simple implementation. Because of its simplicity, Kruskal's algorithm is simple to comprehend and use in various real-world applications, including clustering, network design, and road construction.
Kruskal's approach does have several drawbacks, though. When there are a lot of edges in a thick graph, the sorting step becomes the bottleneck, making it less effective. The disjoint-set data structure must also be managed well to maintain optimal performance.
Ultimately, Kruskal's approach offers a good compromise between simplicity and efficiency, making it a great option for issues involving sparse graphs or edge-centric operations. By being aware of its advantages and disadvantages, developers can choose the best algorithm for the particulars of the graph they are processing.
Kruskal's method can be used to determine a graph's Minimum Spanning Tree (MST). By linking all of a graph's vertices with the least amount of edge weight, it guarantees that there are no cycles.
The main steps are:
The temporal complexity of Kruskal's method is O(E log E), where E is the number of edges. With path compression and union by rank, the union-find operations take O(E α(V)), where α is the inverse Ackermann function and nearly constant. Sorting the edges takes O(E log E).
Kruskal's algorithm uses:
When there are many edges, the sorting step O(E log E) might be expensive, making Kruskal's approach less effective for dense graphs. Prim's technique may be more effective for thick graphs because it incrementally adds edges to the MST.
Complete Guide on String Functions in C - Learn essential string functions in C with syntax, examples, memory rules, and safe practices. Master strlen, strcpy, strcmp, strcat, strstr, and more with clarity. (5 min read, December 29, 2025)
Mastering Insertion Sort in C: Code, Logic, and Applications - Understand insertion sort in C with easy-to-follow logic, code examples, and practical tips. Learn how this sorting technique works in real programs. (6 min read, December 29, 2025)
Quick Sort Algorithm Explained: Steps, Code Examples and Use Cases - Learn the Quick Sort Algorithm with clear steps, partition logic, Python & C++ code examples, and time complexity explained for students and developers. (6 min read, December 28, 2025)
Switch Statement in C: Syntax, Flowchart & Sample Programs - Learn how to use the switch statement in C programming with simple syntax, real-life examples, and use cases. Ideal for beginners and students. (6 min read, December 27, 2025)
Linked List in Data Structure: A Complete Guide - Learn what a Linked List in Data Structure is, its types, operations, advantages, and real-world uses. A complete guide for students and developers. (8 min read, December 27, 2025)
The Ultimate Guide to Binary Search Algorithm in C - Learn the Binary Search Algorithm with steps, examples, and efficiency insights. Understand how it works in C for fast and accurate data searching. (8 min read, December 27, 2025)