# Kruskal

Utilized in the discovery of the minimum spanning tree, this method involves arranging the edges in descending order and sequentially incorporating the smallest unused edge. This process aims to construct a tree encompassing all nodes while adhering to these criteria. 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[2])

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

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

# 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[0])
p2 = find(parent, edge[1])

# 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][2] > graph[j + 1][2]) {
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][0]] = graph[i][0];
parent[graph[i][1]] = graph[i][1];
}

// 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[0]);
int p2 = find(parent, edge[1]);

// 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[2])
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)
g.kruskal_algo()


Previous
Next