Kruskal's Algorithm Implementation in C - MYCPLUS - C and C++ Programming Resources

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.

Key Concepts
Kruskal’s Algorithm Steps
Pseudo code of the Kruskal’s Algorithm
Complexity of Kruskal’s Algorithm
Applications of Kruskal’s Algorithm
C Programming Implementation of Kruskal’s Algorithm
C++ Programming Implementation of Kruskal’s Algorithm
Python 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.

minimum spanning tree (MST) — **Left Image:** The original graph, where the numbers on the edges represent their weights. **Right Image:** The MST of the graph, highlighting the subset of edges that connect all vertices with the minimum total weight.

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

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] &gt; rank[rootY]:
            parent[rootY] = rootX
        else if rank[rootX] &lt; rank[rootY]:
            parent[rootX] = rootY
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

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.

Applications of Kruskal’s Algorithm

Kruskal’s algorithm is significant in data processing and data management because it efficiently finds the Minimum Spanning Tree (MST) of a weighted graph. This has various applications, including:

1. Network Design and Optimization

Used in designing efficient communication networks (e.g., laying out fiber-optic cables, telephone networks, and electrical grids).
Helps in reducing costs by ensuring minimal total weight (cost/distance) for connections.

2. Clustering in Data Mining

Kruskal’s algorithm is used in hierarchical clustering, particularly in single linkage clustering.
Helps group similar data points together based on the shortest connection.

3. Image Processing

Applied in segmentation of images by grouping similar regions based on edge weights.
Used in graph based segmentation techniques.

4. Geographic Information Systems (GIS)

Helps in computing optimal road maps and route planning.
Assists in finding minimum cost paths for transportation networks.

5. Data Management and Distributed Systems

Helps in reducing redundancy in database relationships and query optimization.
Assists in structuring distributed databases to optimize communication.

Used to identify strongly connected components with minimum connection costs.

C Programming Implementation of Kruskal’s Algorithm

Here is the C program that implements this algorithm.

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

#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:

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

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

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;

}

Python Implementation of Kruskal’s Algorithm

Here is a sample implementation of Kruskal’s Algorithm in Python using the Disjoint Set (Union-Find) data structure for efficiency. The edges are sorted by weight to ensure we always pick the smallest edge. It iterates through the edges and adds them to the MST if they don’t form a cycle.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])  # Path compression
        return self.parent[node]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    """
    :param n: Number of nodes in the graph
    :param edges: List of edges (u, v, weight)
    :return: Minimum spanning tree and its cost
    """
    edges.sort(key=lambda x: x[2])  # Sort edges by weight
    ds = DisjointSet(n)
    mst = []
    total_weight = 0

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):  # If adding this edge doesn't form a cycle
            ds.union(u, v)
            mst.append((u, v, weight))
            total_weight += weight

    return mst, total_weight

# Example Graph (Undirected Weighted Graph)
edges = [
    (0, 1, 10), (0, 2, 6), (0, 3, 5),
    (1, 3, 15), (2, 3, 4)
]
num_nodes = 4

# Compute Minimum Spanning Tree
mst, total_weight = kruskal(num_nodes, edges)

# Output
print("Minimum Spanning Tree:", mst)
print("Total Weight of MST:", total_weight)

class DisjointSet:

def __init__(self, n):

self.parent = list(range(n))

self.rank = [0] * n

def find(self, node):

if self.parent[node] != node:

self.parent[node] = self.find(self.parent[node]) # Path compression

return self.parent[node]

def union(self, u, v):

root_u = self.find(u)

root_v = self.find(v)

if root_u != root_v:

if self.rank[root_u] > self.rank[root_v]:

self.parent[root_v] = root_u

elif self.rank[root_u] < self.rank[root_v]:

self.parent[root_u] = root_v

else:

self.parent[root_v] = root_u

self.rank[root_u] += 1

def kruskal(n, edges):

"""

:param n: Number of nodes in the graph

:param edges: List of edges (u, v, weight)

:return: Minimum spanning tree and its cost

"""

edges.sort(key=lambda x: x[2]) # Sort edges by weight

ds = DisjointSet(n)

mst = []

total_weight = 0

for u, v, weight in edges:

if ds.find(u) != ds.find(v): # If adding this edge doesn't form a cycle

ds.union(u, v)

mst.append((u, v, weight))

total_weight += weight

return mst, total_weight

# Example Graph (Undirected Weighted Graph)

edges = [

(0, 1, 10), (0, 2, 6), (0, 3, 5),

(1, 3, 15), (2, 3, 4)

]

num_nodes = 4

# Compute Minimum Spanning Tree

mst, total_weight = kruskal(num_nodes, edges)

# Output

print("Minimum Spanning Tree:", mst)

print("Total Weight of MST:", total_weight)

You can also view implementation of sorting algorithms in C here: Shell Sort, Quick Sort, Insertion Sort, Selection Sort

Kruskal’s Algorithm

Table of Contents

Key Concepts

Kruskal’s Algorithm Steps

Pseudo code of the Kruskal’s Algorithm

Complexity of Kruskal’s Algorithm

Applications of Kruskal’s Algorithm

1. Network Design and Optimization

2. Clustering in Data Mining

3. Image Processing

4. Geographic Information Systems (GIS)

5. Data Management and Distributed Systems

C Programming Implementation of Kruskal’s Algorithm

Output of the C Program

C++ Programming Implementation of Kruskal’s Algorithm

Python Implementation of Kruskal’s Algorithm

About The Author

M. Saqib

Kruskal’s Algorithm

Table of Contents

Key Concepts

Kruskal’s Algorithm Steps

Pseudo code of the Kruskal’s Algorithm

Complexity of Kruskal’s Algorithm

Applications of Kruskal’s Algorithm

1. Network Design and Optimization

2. Clustering in Data Mining

3. Image Processing

4. Geographic Information Systems (GIS)

5. Data Management and Distributed Systems

6. Social Network Analysis

C Programming Implementation of Kruskal’s Algorithm

Output of the C Program

C++ Programming Implementation of Kruskal’s Algorithm

Python Implementation of Kruskal’s Algorithm

About The Author

M. Saqib

Related Posts

Solving the Knapsack Problem with Code Examples

C Programming: File Listing Utility – Directory Structure

Graphical Scientific Calculator with Advance Features

Smith-Waterman Algorithm – The Optimal Pairwise Sequence Alignment Problem