Kruskal Algorithm in C : Concept, Explanation & Example

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. Before going deeper into it, there are a few fundamental concepts to understand. 

A greedy algorithm makes decisions step by step and always choosing the best immediate option without looking ahead. This approach is useful and even 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:

• Huffman coding  where it is used for data compression.
• Dijkstra’s algorithm where it’s used for shortest path in graphs.
• Activity selection problems for scheduling tasks efficiently.

Why Kruskal Algorithm in C is considered Greedy 

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

1. At each step, the algorithm does the following:

2. Picks the smallest edge from the sorted list.

3. Checks if adding it forms a cycle (using the Union-Find algorithm).

4. If no cycle is formed, the edge is added to the MST.

5. This continues until all vertices are connected.

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:

• It is connected  and there is a path between every pair of vertices.
• It has exactly V - 1 edges for a graph with V vertices.
• It contains no cycles.

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 is without going in loops. Spanning trees are applied in network routing, electrical circuits, and designing efficient transportation paths.

Minimum Spanning Tree 

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.

Properties of an MST:

• Unique for a graph with distinct edge weights
• Has exactly V - 1 edges (where V is the number of vertices)
• Ensures the smallest possible sum of edge weights

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. That’s because it processes edges in increasing order and only adds edges that do not form cycles. In the following section we look at minimum spanning tree kruskal algorithm in c and how to get to it.

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. 

For example, consider this graph with 5 vertices and 6 edges and 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 the MST while avoiding cycles.

Cost Table in Kruskal’s Algorithm

In the table:

• Each cell (i, j) represents the weight of the edge between vertices i and j.
• A dash (-) means there is no direct edge between those vertices.
• Diagonal elements are 0 because there is no cost to stay at the same vertex.

Steps To Find MST

• Arrange edges according to weight: Sort all the edges from low weight to high
• Set the MST's initial state to empty.
• 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. 
• Make sure the selected edge does not create a cycle with the previously selected edges.
• Get rid of the edge if it creates a cycle.
• Verify whether the current edge and the spanning tree that has been created thus far constitute a cycle.
• Continue until the tree is finished: Keep adding edges in this way until the MST has precisely V-1 edges, where VV 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. And here is how it is found: 

Step 1: Select the Smallest Edge (A → D, Weight = 1)

The smallest edge in the graph is A → D (1), so we add it first. At this point, only A and D are connected.

Step 2: Add B → C (3)

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:

Step 3: Add C → E (4)

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.

Step 4: Add A → B (5)

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 

Algorithm for this Code

1. Sort all edges in the graph by their weight in ascending order.

2. Initialize a Union-Find structure where each vertex is its own subset.

3. Iterate through the sorted edges and process each edge:

• Check if adding the edge creates a cycle using the Find operation.
• If it does not form a cycle, add it to the Minimum Spanning Tree (MST) and merge the sets using Union.
• If it forms a cycle, ignore it.

4. Repeat the process until the MST contains exactly (V - 1) edges, where V is the number of vertices.

5. Print the edges of the MST along with their weights.

C Program for Kruskal's Algorithm 

#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);
}

Output 

In this kruskal's algorithm in c with output, we can see the edges of the MST being found just as in the diagram above.

Edges in the Minimum Spanning Tree:
A -- 1 -- D
B -- 3 -- C
C -- 4 -- E
A -- 5 -- B
 
 
=== Code Execution Successful ===

How the Code Works

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.

Complexity

Time Complexity: O(ELogE + ELog V) since it involces 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 alway 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.

Kruskal's vs Prim's Algorithm

Here are some of the differences between the two:

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:

Advantages of Kruskal’s Algorithm

• 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(Elog⁡E)O(E \log E), dominates the algorithm's temporal complexity because it focuses on sorting edges and processing them in order of weight, where EE 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. 

Disadvantages of Kruskal’s Algorithm

• 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 EE can reach O(V2)O(V^2) (where VV 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: 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:

1. Network Design

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.

2. Data Clustering

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.

3. Image Segmentation

Images can be treated like graphs, where each pixel is a node. Kruskal’s algorithm helps group similar region which is useful in tasks like face detection or medical image analysis.

4. Route Planning in Maps

It helps in planning the best paths for transportation systems like roads, railways, or delivery routes. This makes travel more cost-effective.

5. Database Optimization

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. 

1. What is Kruskal’s algorithm used for?

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. 

2. What are the main steps in Kruskal’s algorithm?

The main steps are:

• Sort all edges by weight.
• Initialise disjoint sets for each vertex using Union-Find.
• Iterate through edges: For each edge, check if it connects two different sets (no cycle). If it does, add it to the MST and merge the sets using the union operation.
• Repeat until the MST has V−1V-1 edges (where VV is the number of vertices).

3. What is the time complexity of Kruskal’s algorithm?

The temporal complexity of Kruskal's method is O(Elog⁡E)O(E \log E), where EE is the number of edges. With path compression and union by rank, the union-find operations take O(Eα(V))O(E \alpha(V)), where α\alpha is the inverse Ackermann function and nearly constant. Sorting the edges takes O(Elog⁡E)O(E \log E). 

4. What data structures are used in Kruskal’s algorithm?

Kruskal’s algorithm uses:

• Edge list: To store the edges with their weights.
• Disjoint-set (Union-Find): To keep track of connected components and prevent cycles.

5. Can Kruskal’s algorithm work for dense graphs?

When there are many edges, the sorting step O(Elog⁡E)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.