Kruskal | Agung Pambudi

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