Data Structure and Algorithm
Kruskal's Algorithm for Finding the Minimum Spanning Tree in a Graph
 Introduction
 Properties of the Minimum Spanning Tree
 Kruskal’s Algorithm for Minimum Spanning Tree
 Time Complexity
 Spanning Tree with Minimum Product
 Maximum Spanning Tree
 Applications of the Algorithm
 Run C Programming Online Compiler
¶Introduction
A Minimum Spanning Tree (MST)
is a tree containing subset of the edges of a connected, undirected graph that connects all the vertices without any cycles and with the minimum possible total edge weight. Essentially, it is a tree that spans all the vertices in the graph and has the smallest possible sum of edge weights.
Imagine a telecommunications company wanting to connect several cities with fiber optic cables. The goal is to minimize the total cost of the cables while ensuring that all cities are connected. We can just find the MST of the network to solve this problem problem. MSTs are also crucial in various fields such as network design, including computer, telecommunications, and transportation networks, where minimizing the cost of connecting a set of points is essential.
¶Properties of the Minimum Spanning Tree
¶Uniqueness of the Minimum Spanning Tree
A minimum spanning tree of a graph is unique if the weights of all the edges are distinct. When the edge weights are distinct, there is only one way to connect all the vertices with the minimum possible total edge weight without forming any cycles. However, if there are edges with equal weights, there may be multiple minimum spanning trees for the same graph. Different algorithms or even different runs of the same algorithm might produce different MSTs, but all will have the same total weight.
¶Maximum Edge Weight in the Minimum Spanning Tree
In a minimum spanning tree of a graph, the maximum weight of an edge is the minimum possible from all possible spanning trees of that graph. This property follows from the validity of Kruskal’s algorithm. Kruskal’s algorithm builds the MST by always choosing the smallest available edge that does not form a cycle, ensuring that the largest edge in the resulting MST is as small as possible. Consequently, among all possible spanning trees, the MST will have the smallest possible maximum edge weight.
¶Kruskal’s Algorithm for Minimum Spanning Tree
Kruskal’s algorithm is a greedy algorithm to find the MST of a connected, weighted, undirected graph. It works by sorting all the edges in the graph in nondecreasing order of their weight and then adding edges one by one to the MST, ensuring that no cycles are formed.
 Create a forest where each vertex is a separate tree.
 Sort all the edges in nondecreasing order of their weights.
 Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far using a disjointset data structure. If a cycle is not formed, include this edge in the MST. Otherwise, discard it. We can check cycle formation easily using DSU data structure.
 Continue the process for all the remaining edges until we add
(V  1)
edges in the MST.
¶Implementation in C++ with DSU
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int u, v, weight;
bool operator<(Edge const& other) {
return weight < other.weight;
}
};
class DSU {
vector<int> parent, rank;
public:
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int u) {
if (u != parent[u]) {
parent[u] = find(parent[u]);
}
return parent[u];
}
void unite(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
if (rank[u] < rank[v]) {
swap(u, v);
}
parent[v] = u;
if (rank[u] == rank[v]) {
rank[u]++;
}
}
}
};
int main() {
int n = 4; // Number of vertices
vector<Edge> edges = {
{0, 1, 10},
{0, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};
sort(edges.begin(), edges.end());
DSU dsu(n);
int cost = 0;
vector<Edge> result;
for (Edge &e : edges) {
if (dsu.find(e.u) != dsu.find(e.v)) {
cost += e.weight;
result.push_back(e);
dsu.unite(e.u, e.v);
}
}
cout << "Cost of MST: " << cost << endl;
for (Edge &e : result) {
cout << e.u << "  " << e.v << " == " << e.weight << endl;
}
return 0;
}
Cost of MST: 19
2  3 == 4
0  3 == 5
0  1 == 10
¶Time Complexity
The time complexity of Kruskal’s algorithm primarily depends on the sorting step and the unionfind operations.

Sorting the Edges:
O(E log E)
whereE
is the number of edges. 
UnionFind Operations: The union and find operations have an almost constant time complexity,
O(α(V))
, whereα( )
is the inverse Ackermann function, which grows very slowly.
Thus, the overall time complexity of Kruskal’s algorithm isO(E log E)
, since O(E α(V))
is pretty smaller than O(E log E)
,
¶Spanning Tree with Minimum Product
Given a weighted graph, find the spanning tree that minimizes the product of edge weights.
Solution :
Surprisingly, determining the set of edges that minimizes the total weight of a spanning tree also results in minimizing the product of those edge weights. This connection between addition and multiplication is a fascinating property of minimum spanning trees.
¶Maximum Spanning Tree
Given a weighted graph, find the maximum spanning tree.
Solution :
To find the maximum spanning tree of a graph, a straightforward approach involves transforming the problem into a minimum spanning tree problem. This is achieved by negating the weight of every edge in the graph. Once the weights are inverted, a standard minimum spanning tree algorithm can be applied to determine the maximum spanning tree of the original graph.
¶Applications of the Algorithm
 Network Design : Used in designing networks such as telecommunication, computer networks, water supply networks, and electrical grids to minimize the cost of connecting various nodes.
 Civil Engineering : Helps in planning the layout of roads, railways, and pipelines, ensuring minimal construction cost.
 Computer Graphics : Employed in constructing the mesh of a 3D object by connecting vertices with minimal cost.
 Electrical Circuits : Designing circuits with minimal wire length.
 Clustering : Creating clusters of data points by finding the minimum spanning tree of a similarity graph.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
SingleSource Shortest Paths Algorithm  Dijkstra's Algorithm
Introduction to Binary Search with Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
18

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development