## Algorithm

It seems like you're referring to Kruskal's algorithm, which is a popular algorithm in computer science, specifically used for finding the minimum spanning tree of a connected, undirected graph. A minimum spanning tree is a subset of the edges of a graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.

Kruskal's algorithm works by sorting all the edges in the graph in non-decreasing order of their weights and then adding them to the spanning tree one by one, while ensuring that no cycles are formed. Here's a high-level overview of the algorithm:

1. Sort Edges: Sort all the edges in the graph in non-decreasing order of their weights.

2. Initialize: Create an empty graph to represent the minimum spanning tree.

3. Iterate through Edges: Iterate through the sorted edges, and for each edge, check if adding it to the current minimum spanning tree would create a cycle. If not, add the edge to the spanning tree.

4. Stop: Continue this process until the spanning tree has V−1 edges, where V is the number of vertices in the original graph.

Kruskal's algorithm is greedy and has a time complexity of O(Elogā”E), where E is the number of edges in the graph. It's worth noting that Kruskal's algorithm can be efficient for sparse graphs where E is much less than V2.

## Code Examples

### #1 Kruskal's implement in Python

Code - Python Programming

class UnionFind:
def __init__(self, vertices):
self.parent = {vertex: vertex for vertex in vertices}
self.rank = {vertex: 0 for vertex 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, vertex1, vertex2):
root1 = self.find(vertex1)
root2 = self.find(vertex2)

if 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((weight, vertex, neighbor))

edges.sort()  # Sort edges by weight in ascending order

minimum_spanning_tree = []
union_find = UnionFind(graph.keys())

for edge in edges:
weight, vertex1, vertex2 = edge
if union_find.find(vertex1) != union_find.find(vertex2):
minimum_spanning_tree.append((vertex1, vertex2, weight))
union_find.union(vertex1, vertex2)

return minimum_spanning_tree

# Example usage:
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}

result = kruskal(graph)
print("Minimum Spanning Tree:", result)

Copy The Code &

### #2 Kruskal's implement in Java

Code - Java Programming

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Edge {
int source, destination, weight;

public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}

class Graph {
int vertices;
List < Edge> edges;

public Graph(int vertices) {
this.vertices = vertices;
this.edges = new ArrayList < >();
}

public void addEdge(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
edges.add(edge);
}

public void kruskalMST() {
// Sort edges by weight in ascending order
Collections.sort(edges, Comparator.comparingInt(e -> e.weight));

int[] parent = new int[vertices];
for (int i = 0; i  <  vertices; i++) {
parent[i] = i;
}

List < Edge> result = new ArrayList<>();

for (Edge edge : edges) {
int root1 = find(parent, edge.source);
int root2 = find(parent, edge.destination);

if (root1 != root2) {
result.add(edge);
union(parent, root1, root2);
}
}

// Print the MST edges
System.out.println("Minimum Spanning Tree:");
for (Edge edge : result) {
System.out.println(edge.source + " - " + edge.destination + " : " + edge.weight);
}
}

private int find(int[] parent, int vertex) {
if (parent[vertex] != vertex) {
parent[vertex] = find(parent, parent[vertex]);
}
return parent[vertex];
}

private void union(int[] parent, int root1, int root2) {
parent[root1] = root2;
}
}

public class KruskalsAlgorithm {
public static void main(String[] args) {
int vertices = 4;
Graph graph = new Graph(vertices);

// Add edges to the graph
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 3, 4);

// Find and print the Minimum Spanning Tree
graph.kruskalMST();
}
}

Copy The Code &

### #3 Kruskal's implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge in the graph
struct Edge {
int src, dest, weight;
};

// Structure to represent a subset for union-find
struct Subset {
int parent;
int rank;
};

// Function to find the set of an element in a disjoint set
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}

// Function to perform union of two subsets
void unionSets(struct Subset subsets[], int x, int y) {
int rootX = find(subsets, x);
int rootY = find(subsets, y);

if (subsets[rootX].rank  <  subsets[rootY].rank)
subsets[rootX].parent = rootY;
else if (subsets[rootX].rank > subsets[rootY].rank)
subsets[rootY].parent = rootX;
else {
subsets[rootX].parent = rootY;
subsets[rootY].rank++;
}
}

// Function to compare two edges based on their weights
int compareEdges(const void* a, const void* b) {
return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

// Function to run Kruskal's algorithm
void kruskalMST(struct Edge edges[], int V, int E) {
// Allocate memory for subsets
struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));

// Initialize subsets
for (int i = 0; i  <  V; i++) {
subsets[i].parent = i;
subsets[i].rank = 0;
}

// Sort the edges in non-decreasing order by weight
qsort(edges, E, sizeof(edges[0]), compareEdges);

printf("Minimum Spanning Tree using Kruskal's algorithm:\n");

int mstWeight = 0; // Total weight of the MST

for (int i = 0, j = 0; j  <  V - 1 && i < E; i++) {
// Pick the smallest edge
struct Edge nextEdge = edges[i];

// Find the sets of the source and destination vertices
int x = find(subsets, nextEdge.src);
int y = find(subsets, nextEdge.dest);

// If including this edge does not cause a cycle, add it to the MST
if (x != y) {
printf("(%d, %d) -> %d\n", nextEdge.src, nextEdge.dest, nextEdge.weight);
mstWeight += nextEdge.weight;
unionSets(subsets, x, y);
j++;
}
}

printf("Total Weight of MST: %d\n", mstWeight);

// Free allocated memory
free(subsets);
}

int main() {
// Example graph representation
int V = 4; // Number of vertices
int E = 5; // Number of edges
struct Edge edges[] = {
{0, 1, 10},
{0, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};

// Run Kruskal's algorithm
kruskalMST(edges, V, E);

return 0;
}

Copy The Code &

### #4 Kruskal's implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Structure to represent an edge
struct Edge {
int source, destination, weight;

// Comparator function for sorting edges based on weight
bool operator < (const Edge& other) const {
return weight < other.weight;
}
};

class Kruskal {
private:
int vertices;
vector < Edge> edges;

public:
Kruskal(int v) : vertices(v) {}

// Add an edge to the graph
void addEdge(int src, int dest, int weight) {
edges.push_back({src, dest, weight});
}

// Find set of an element i
int findSet(vector<int>& parent, int i) {
if (parent[i] == -1)
return i;
return findSet(parent, parent[i]);
}

// Union of two sets
void unionSets(vector<int>& parent, int x, int y) {
int xroot = findSet(parent, x);
int yroot = findSet(parent, y);
parent[xroot] = yroot;
}

// Function to run Kruskal's algorithm
void kruskalMST() {
// Sort edges in non-decreasing order of weight
sort(edges.begin(), edges.end());

vector<int> parent(vertices, -1);

for (const Edge& edge : edges) {
int x = findSet(parent, edge.source);
int y = findSet(parent, edge.destination);

// If including this edge doesn't cause a cycle, include it in the MST
if (x != y) {
cout << edge.source << " - " << edge.destination << " : " << edge.weight << endl;
unionSets(parent, x, y);
}
}
}
};

int main() {
Kruskal g(4);

// Example graph
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 6);
g.addEdge(0, 3, 5);
g.addEdge(1, 3, 15);
g.addEdge(2, 3, 4);

cout << "Edges in the Minimum Spanning Tree:\n";
g.kruskalMST();

return 0;
}

Copy The Code &
Advertisements

## Demonstration

Kruskal's Data Structure and Algorithm