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[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()

Previous
Next