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.
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