# Kruskal

Here’s an example implementation of Kruskal’s algorithm:

Python

# Define a helper function to find the parent of a node in a set
def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

# Define the main function that implements Kruskal's algorithm
def kruskal(graph):
# Sort the edges by weight in non-decreasing order
edges = sorted(graph, key=lambda x: x)

# Initialize an empty set of parent nodes
parent = dict()

# Create a parent node for each vertex
for edge in edges:
parent[edge] = edge
parent[edge] = edge

# Initialize an empty list to store the minimum spanning tree
mst = []

# Iterate over the edges in the sorted order
for edge in edges:
# Find the parent of each node in the edge
p1 = find(parent, edge)
p2 = find(parent, edge)

# If the parent nodes are different, add the edge to the minimum spanning tree
if p1 != p2:
mst.append(edge)

# Union the sets of nodes by setting one node's parent to the other node's parent
parent[p1] = p2

return mst


This implementation assumes that the graph is represented as a list of tuples, where each tuple represents an edge with the format (node1, node2, weight). The kruskal function takes this list as input, and returns a list of tuples representing the edges in the minimum spanning tree.

C


#include <stdlib.h>

// Define a helper function to find the parent of a node in a set
int find(int parent[], int i) {
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}

// Define the main function that implements Kruskal's algorithm
int** kruskal(int** graph, int numEdges) {
// Sort the edges by weight in non-decreasing order
for (int i = 0; i < numEdges - 1; i++) {
for (int j = 0; j < numEdges - i - 1; j++) {
if (graph[j] > graph[j + 1]) {
int* temp = graph[j];
graph[j] = graph[j + 1];
graph[j + 1] = temp;
}
}
}

// Initialize an empty array of parent nodes
int* parent = (int*)malloc(numEdges * sizeof(int));

// Create a parent node for each vertex
for (int i = 0; i < numEdges; i++) {
parent[graph[i]] = graph[i];
parent[graph[i]] = graph[i];
}

// Initialize an empty array to store the minimum spanning tree
int** mst = (int**)malloc(numEdges * sizeof(int*));
int mstSize = 0;

// Iterate over the edges in the sorted order
for (int i = 0; i < numEdges; i++) {
int* edge = graph[i];

// Find the parent of each node in the edge
int p1 = find(parent, edge);
int p2 = find(parent, edge);

// If the parent nodes are different, add the edge to the minimum spanning tree
if (p1 != p2) {
mst[mstSize] = edge;
mstSize++;

// Union the sets of nodes by setting one node's parent to the other node's parent
parent[p1] = p2;
}
}

// Resize the mst array to its actual size
mst = (int**)realloc(mst, mstSize * sizeof(int*));

// Free the parent array
free(parent);

return mst;
}


Rust

fn find(parent: &mut Vec<usize>, i: usize) -> usize {
if parent[i] == i {
return i;
}
parent[i] = find(parent, parent[i]);
parent[i]
}

fn kruskal(graph: &Vec<(usize, usize, i32)>) -> Vec<(usize, usize, i32)> {
// Sort the edges by weight in non-decreasing order
let mut edges = graph.clone();
edges.sort_by_key(|x| x.2);

// Initialize an empty set of parent nodes
let mut parent: Vec<usize> = Vec::new();

// Create a parent node for each vertex
for edge in &edges {
parent.resize_with(edge.0.max(edge.1) + 1, || parent.len());
parent[edge.0] = edge.0;
parent[edge.1] = edge.1;
}

// Initialize an empty vector to store the minimum spanning tree
let mut mst = Vec::new();

// Iterate over the edges in the sorted order
for edge in &edges {
// Find the parent of each node in the edge
let p1 = find(&mut parent, edge.0);
let p2 = find(&mut parent, edge.1);

// If the parent nodes are different, add the edge to the minimum spanning tree
if p1 != p2 {
mst.push(*edge);

// Union the sets of nodes by setting one node's parent to the other node's parent
parent[p1] = p2;
}
}

mst
}


Explanation:

• fn find(parent: &mut Vec, i: usize) -> usize is a helper function that finds the parent of a node in a set. It takes a mutable reference to a vector parent that contains the parent nodes for each vertex, and an index i for the node whose parent to find. It returns the parent node index for i.
• fn kruskal(graph: &Vec<(usize, usize, i32)>) -> Vec<(usize, usize, i32)> is the main function that implements Kruskal’s algorithm. It takes a reference to a vector of tuples graph that represent the edges of a weighted undirected graph. Each tuple contains the indices of the two vertices that the edge connects, and the weight of the edge. It returns a vector of tuples that represent the edges of the minimum spanning tree.
• let mut edges = graph.clone(); edges.sort_by_key(|x| x.2); creates a mutable copy of the input graph and sorts the edges by their weights in non-decreasing order.
• let mut parent: Vec = Vec::new(); initializes an empty vector to store the parent nodes for each vertex.
• parent.resize_with(edge.0.max(edge.1) + 1, || parent.len()); resizes parent to accommodate the indices of the vertices in the edges. It ensures that the size of parent is at least the maximum vertex index plus one. It uses || parent.len() as a closure to initialize new elements of parent to the current length of parent.
• parent[edge.0] = edge.0; parent[edge.1] = edge.1; initializes the parent nodes for the vertices in each edge.
• let mut mst = Vec::new(); initializes an empty vector to store the edges of the minimum spanning tree.
• for edge in &edges { … } iterates
Click to view another code.

Python

class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []

self.graph.append([u, v, w])

# Search function
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])

def apply_union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1

# Applying Kruskal’s algorithm
def kruskal_algo(self):
result = []
i, e = 0, 0
self.graph = sorted(self.graph, key=lambda item: item)
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e = e + 1
result.append([u, v, w])
self.apply_union(parent, rank, x, y)
for u, v, weight in result:
print("%d - %d: %d" % (u, v, weight))

g = Graph(6)