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 = []
def add_edge(self, u, v, w):
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.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 0, 4)
g.add_edge(2, 0, 4)
g.add_edge(2, 1, 2)
g.add_edge(2, 3, 3)
g.add_edge(2, 5, 2)
g.add_edge(2, 4, 4)
g.add_edge(3, 2, 3)
g.add_edge(3, 4, 3)
g.add_edge(4, 2, 4)
g.add_edge(4, 3, 3)
g.add_edge(5, 2, 2)
g.add_edge(5, 4, 3)
g.kruskal_algo()