### Kruskal's Algorithm for Minimum Spanning Tree

**Kruskal's Algorithm for Minimum Spanning Tree**

# Overview:

Kruskal's algorithm is a greedy algorithm used for finding the Minimum Spanning Tree (MST) of a connected, undirected graph. A Minimum Spanning Tree is a subset of the edges of a graph that connects all the vertices without any cycles and with the minimum possible total edge weight.

- Kruskal's algorithm relies on efficiently checking for cycles, which is often done using a Union-Find data structure.
- The Union-Find data structure keeps track of a partition of a set into disjoint subsets and supports two operations: Union (to merge two subsets) and Find (to determine which subset an element belongs to).

**Time Complexity:**

- The overall time complexity of Kruskal's algorithm is often dominated by the sorting of edges, resulting in O(E log E) time complexity, where E is the number of edges.

**Space Complexity:**

- The space complexity is typically O(V + E), where V is the number of vertices.

**Key Properties:**

- Kruskal's algorithm is a greedy algorithm that consistently chooses the smallest edge that does not form a cycle.
- The resulting Minimum Spanning Tree is not unique, as long as it satisfies the conditions of spanning all vertices without cycles and with the minimum possible total weight.

Kruskal's algorithm is widely used and efficient for finding minimum spanning trees in various applications, such as network design and clustering. It's known for its simplicity and effectiveness in solving the MST problem.

# Python code:

```
class UnionFind:
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}
def find(self, vertex):
if self.parent[vertex] != vertex:
self.parent[vertex] = self.find(self.parent[vertex])
return self.parent[vertex]
def union(self, root1, root2):
if self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
elif self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
else:
self.parent[root1] = root2
self.rank[root2] += 1
def kruskal(graph):
edges = []
for vertex in graph:
for neighbor, weight in graph[vertex]:
edges.append((vertex, neighbor, weight))
edges.sort(key=lambda x: x[2]) # Sort edges by weight
vertices = set()
for edge in edges:
vertices.add(edge[0])
vertices.add(edge[1])
minimum_spanning_tree = []
union_find = UnionFind(vertices)
for edge in edges:
root1 = union_find.find(edge[0])
root2 = union_find.find(edge[1])
if root1 != root2:
minimum_spanning_tree.append(edge)
union_find.union(root1, root2)
return minimum_spanning_tree
# Example usage:
graph = {
'A': [('B', 4), ('H', 8)],
'B': [('A', 4), ('C', 8), ('H', 11)],
'C': [('B', 8), ('D', 7), ('F', 4), ('I', 2)],
'D': [('C', 7), ('E', 9), ('F', 14)],
'E': [('D', 9), ('F', 10)],
'F': [('C', 4), ('D', 14), ('E', 10), ('G', 2)],
'G': [('F', 2), ('H', 1), ('I', 6)],
'H': [('A', 8), ('B', 11), ('G', 1), ('I', 7)],
'I': [('C', 2), ('G', 6), ('H', 7)]
}
result = kruskal(graph)
print("Minimum Spanning Tree:")
for edge in result:
print(edge)
```

## Step-By-Step explanation:

1.The class represents a Union-Find data structure. It has methods for initializing the structure (—init—), finding the root of a set (find), and performing union operation (union). The find method uses path compression to optimize future finds.

2.The kruskal function takes a graph as input, where each vertex is associated with a list of its neighbors and corresponding edge weights.

- It initializes an empty list edges to store all edges and populates it by iterating through the vertices and their neighbors.
- The edges are then sorted in ascending order based on their weights.
- It initializes an empty set vertices to keep track of all vertices.
- The minimum spanning tree is stored in the list minimum spanning tree.
- A Union-Find data structure is created using the UnionFind class, and each vertex is initially its own set.
- The sorted edges are iterated, and for each edge, the roots of the sets containing its two vertices are determined.
- If the roots are different (i.e., adding the edge does not create a cycle), the edge is added to the minimum spanning tree, and the two sets are unioned.
- The final minimum spanning tree is returned.

- An example graph is provided, and the kruskal function is called to find the minimum spanning tree.
- The resulting minimum spanning tree edges are printed.

# Java code:

```
import java.util.*;
class Edge implements Comparable<Edge> {
int source;
int destination;
double weight;
public
Edge(int source, int destination, double
weight)
{
this.source = source;
this.destination = destination;
this.weight = weight;
}
@Override
public
int
compareTo(Edge other)
{
return Double.compare(this.weight, other.weight);
}
}
class
DisjointSet
{
private
int[] parent;
public
DisjointSet(int n)
{
parent = new
int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public
int
find(int u)
{
if (u == parent[u]) {
return u;
}
return parent[u] = find(parent[u]);
}
public
void
union(int u, int v) {
int uRoot = find(u);
int vRoot = find(v);
if (uRoot != vRoot) {
parent[uRoot] = vRoot;
}
}
}
public class KruskalMST {
public static List<Edge> kruskalMST(List<Edge> edges, int numVertices) {
List<Edge> mst = new ArrayList<>();
Collections.sort(edges);
DisjointSet ds = new DisjointSet(numVertices);
for (Edge edge : edges) {
if (ds.find(edge.source) != ds.find(edge.destination)) {
mst.add(edge);
ds.union(edge.source, edge.destination);
}
}
return mst;
}
public static void main(String[] args) {
// Add your graph data here
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 10));
edges.add(new Edge(0, 2, 6));
edges.add(new Edge(1, 2, 5));
edges.add(new Edge(1, 3, 15));
edges.add(new Edge(2, 3, 4));
int numVertices = 4;
List<Edge> mst = kruskalMST(edges, numVertices);
for (Edge edge : mst) {
System.out.println(edge.source + "-" + edge.destination + " " + edge.weight);
}
}
}
```

## Step-By-Step Explanation:

Class Definition:`Edge`

- The
class represents an edge in the graph.`Edge`

- It implements the
interface to enable sorting based on edge weights.`Comparable`

### 1.2. Constructor:

- The constructor initializes the source, destination, and weight of the edge.

### 1.3. `compareTo`

Method:

`compareTo`

- The
method is overridden to compare edges based on their weights.`compareTo`

- It returns a negative integer, zero, or a positive integer if the current object is less than, equal to, or greater than the specified object (the
edge).`other`

### 2.`DisjointSet`

Class Definition:

`DisjointSet`

- The
class represents a disjoint-set data structure (also known as Union-Find).`DisjointSet`

- It is used in Kruskal's algorithm for efficient cycle detection.

### 2.2. Constructor:

- The constructor initializes the parent array such that each element is its own parent initially.

### 2.3. `find`

Method:

`find`

- The
method performs the find operation in the disjoint-set data structure.`find`

- It uses path compression to find the root of the set to which the element
belongs.`u`

### 2.4. `union`

Method:

`union`

- The
method performs the union operation in the disjoint-set data structure.`union`

- It joins the sets containing elements
and`u`

by making the root of one set the parent of the root of the other set.`v`

### 3. `kruskalMST`

Method:

`kruskalMST`

- The
method implements Kruskal's algorithm to find the Minimum Spanning Tree (MST).`kruskalMST`

- It sorts the edges in ascending order based on their weights.
- It uses the
class for efficient cycle detection.`DisjointSet`

- It iterates through the sorted edges, adding an edge to the MST only if it does not create a cycle.

### 3.2. `main`

Method:

`main`

- The
method is the entry point of the program.`main`

- It initializes a list of edges representing a graph and the number of vertices.
- It calls the
method to find the MST and prints the result.`kruskalMST`

**4. Running the Code:**

- The
method creates a sample graph with edges and vertices.`main`

- It then calls
to find the Minimum Spanning Tree.`kruskalMST`

- The resulting MST edges are printed in the format "source-destination weight."

# C++ Code:

```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure to represent an edge
struct Edge {
int source;
int destination;
double weight;
};
// Comparator function for sorting edges by weight
bool compare(const Edge& a, const Edge& b) {
return a.weight < b.weight;
}
// Disjoint-set data structure with union-find
class DisjointSet {
vector<int> parent;
vector<int> rank;
public:
DisjointSet(int n) : parent(n), rank(n, 1) {
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int
find(int u)
{
if (u == parent[u]) {
return u;
}
return parent[u] = find(parent[u]);
}
void unionSet(int u, int v)
{
int uRoot = find(u);
int vRoot = find(v);
if (uRoot == vRoot) {
return;
}
if (rank[uRoot] < rank[vRoot]) {
parent[uRoot] = vRoot;
} else
if (rank[uRoot] > rank[vRoot]) {
parent[vRoot] = uRoot;
} else {
parent[vRoot] = uRoot;
rank[uRoot]++;
}
}
};
// Kruskal's algorithm to find MST
vector<Edge> kruskalMST(vector<Edge>& edges, int numVertices) {
vector<Edge> mst;
sort(edges.begin(), edges.end(), compare);
DisjointSet ds(numVertices);
for (const Edge& edge : edges) {
if (ds.find(edge.source) != ds.find(edge.destination)) {
ds.unionSet(edge.source, edge.destination);
mst.push_back(edge);
}
}
return mst;
}
int main() {
// Add your graph data here
vector<Edge> edges;
edges.push_back({0, 1, 10});
edges.push_back({0, 2, 6});
edges.push_back({1, 2, 5});
edges.push_back({1, 3, 15});
edges.push_back({2, 3, 4});
int numVertices = 4;
vector<Edge> mst = kruskalMST(edges, numVertices);
for (const Edge& edge : mst) {
cout << edge.source << " - " << edge.destination << " (" << edge.weight << ")" << endl;
}
return 0;
}
```

## Step-By-Step Explanation:

Statements:`#include`

- The
statements are used to include necessary header files.`#include`

is included for input/output operations, and`iostream`

and`vector`

are included for working with vectors and sorting, respectively.`algorithm`

`using namespace std;`

- The
statement allows the use of standard C++ identifiers (such as`using namespace std;`

and`cout`

) without the`endl`

prefix.`std::`

****2. Edge Structure:**

The ** Edge** structure represents an edge in a graph, containing information about the source vertex, destination vertex, and weight of the edge.

****3. compare Function:**

The ** compare** function is a comparator used for sorting edges. It returns

**if the weight of edge**

`true`

**is less than the weight of edge**

`a`

**.**

`b`

****4. DisjointSet Class:**

- The
class represents a disjoint-set data structure (also known as Union-Find).`DisjointSet`

- It contains vectors for storing parent pointers and ranks of elements.

4.2. Constructor:

- The constructor initializes the parent vector such that each element is initially its own parent, and the rank vector is initialized with 1.

4.3. ** find** Method:

- The
method performs the find operation in the disjoint-set data structure. It uses path compression to find the root of the set to which the element`find`

belongs.`u`

4.4. ** unionSet** Method:

- The
method performs the union operation in the disjoint-set data structure. It joins the sets containing elements`unionSet`

and`u`

by making the root of one set the parent of the root of the other set.`v`

****5. kruskalMST Function:**

- The
function implements Kruskal's algorithm to find the Minimum Spanning Tree (MST) of a graph.`kruskalMST`

- It sorts the edges based on their weights using the
function.`compare`

- It uses the
class to efficiently detect and avoid cycles.`DisjointSet`

- It iterates through the sorted edges, adding an edge to the MST only if it does not create a cycle.

****6. main Function:**

- The
function is the entry point of the program.`main`

- It initializes a vector of edges representing a graph and the number of vertices.
- It calls the
function to find the MST and prints the result.`kruskalMST`

**7. Running the Code:**

- The
function creates a sample graph with edges and vertices.`main`

- It then calls
to find the Minimum Spanning Tree.`kruskalMST`

- The resulting MST edges are printed in the format "source - destination (weight)."

# Real-World Applications of Kruskals Algorithm:

**Network Design:****Telecommunications Networks:**Kruskal's algorithm can be used to lay down the most cost-effective network of cables or fiber optics to connect various communication points.**Computer Networks:**In computer networks, where routers or switches need to be connected, Kruskal's algorithm helps minimize the cost or latency of data transmission.

**Circuit Design:****Printed Circuit Boards (PCBs):**In electronics, Kruskal's algorithm can be applied to design PCBs by connecting components with traces to minimize the total length of connections.

**Transportation Networks:****Road Networks:**For designing road systems between cities or towns to minimize construction costs.**Railway Networks:**To lay down tracks between stations with the least overall cost.

**Water Supply Networks:****Pipelines:**Kruskal's algorithm can be used to design water supply networks by minimizing the total length of pipelines required.

**Robotics and Sensor Networks:****Robotics Path Planning:**In robotics, Kruskal's algorithm can be used to find the most efficient path for a robot to traverse a set of locations.**Sensor Networks:**For deploying a set of sensors in an area to monitor various points with minimal wiring or connectivity costs.

**Image Segmentation:****Medical Imaging:**Kruskal's algorithm can be applied in medical image segmentation, where pixels or regions are connected based on similarity to create a meaningful representation.

**Power Distribution Networks:****Electric Power Grids:**Kruskal's algorithm can help in designing the power distribution network by connecting power stations and substations with the least overall cost.

**Spanning Tree Protocol in Computer Networks:****Ethernet Networks:**In computer networks, Kruskal's algorithm is used as part of the Spanning Tree Protocol to ensure loop-free topologies, preventing broadcast storms.

**Molecular Structure Determination:****Chemistry and Bioinformatics:**In determining the structure of molecules, Kruskal's algorithm can be applied to identify the most important connections between atoms.

**Cluster Analysis:****Data Mining:**Kruskal's algorithm can be employed in cluster analysis to identify relationships and dependencies between data points.