Kruskal Algorithm for Finding the Minimum Spanning Tree

Posted on 2024-04-29 Views: Word count in article: 1.1k Reading time ≈ 4 mins.

For obtaining the minimum spanning tree, the Prim algorithm has been introduced before, and here is another algorithm: Kruskal algorithm.

Kruskal Algorithm steps

Step 1: Sorts all edges in the graph by weight from smallest to largest.
Step 2: Try adding edges to the tree from smallest to largest, and if the newly added edge forms a loop with other edges in the tree, discard the edge and continue trying the other edges.
Step 3: If $n-1$ edges are added to the tree, the minimum spanning tree is built, where $n$ is the number of vertices of the graph.

Note that in the process of adding edges to the tree, Disjoint Set Union (DSU) is used to determine if a loop is formed.

Example

Take this undirected weighted graph above as an example to show the process of the Kruskal algorithm.

First, sort all edges in order of weight, from smallest to largest. Select the edge with the lowest weight which is $AB$ here. If there are multiple edges with the lowest weight, select any one. As shown below:

Then, select the edge $AD$ with the lowest weight to add to the tree. As shown below:

Then, select the edge $CF$ with the lowest weight to add to the tree. As shown below:

Then, select the edge $AC$ with the lowest weight to add to the tree. As shown below:

Then, select the edge $AE$ with the lowest weight to add to the tree. As shown below:

Then, select the edge $FG$ with the lowest weight to add to the tree. The original graph had 7 vertices, and now there are 6 edges in the tree, so the minimum spanning tree is built. As shown below:

Finally, we can get the following minimum spanning tree:

Code

The Kruskal algorithm is implemented using Python.

import heapq

# Disjoint Set Union functions
def find(all_node_parent, node):
    if all_node_parent[node] != node:
        all_node_parent[node] = find(all_node_parent, all_node_parent[node])
    return all_node_parent[node]

def union(all_node_parent, node_1, node_2):
    root_1 = find(all_node_parent, node_1)
    root_2 = find(all_node_parent, node_2)

    if root_1 != root_2:
        all_node_parent[root_2] = root_1

# Kruskal algorithm
def kruskal(adjacency_table_map):
    # Use priority queue to store candidate edges, sorted by weight
    candidate_edges_pq = []
    for curr_node, neighbors in adjacency_table_map.items():
        for neighbor_node, weight in neighbors.items():
            heapq.heappush(candidate_edges_pq, (weight, curr_node, neighbor_node))

    # Initialize the Minimum Spanning Tree with an empty edge list and total weight of zero
    mst_edges_list = []
    total_weight = 0

    # Initialize the parent node of all nodes, and this will be used in the Disjoint Set Union functions
    node_parent = {node: node for node in adjacency_table_map}

    while len(candidate_edges_pq) > 0:
        # Pop the edge with the minimum weight from the priority queue
        weight, curr_node, next_node = heapq.heappop(candidate_edges_pq)

        # if two nodes are in the same set, a loop will be formed when the edge is added to the tree
        if find(node_parent, curr_node) != find(node_parent, next_node):
            # Merge two disjoint sets into a single set
            union(node_parent, curr_node, next_node)

            # Add the edge to the tree
            mst_edges_list.append((weight, curr_node, next_node))
            total_weight += weight
            print("The edge with the lowest weight selected this time : " + str(curr_node) + "-" + str(next_node)
                  + ", weight: " + str(weight) + ". Add it to the tree.")
        else:
            print("The edge with the lowest weight selected this time : " + str(curr_node) + "-" + str(next_node)
                  + ", weight: " + str(weight) + ". Discard it because it will form a cycle.")

        # Check if the tree is complete (If the graph has n vertices, the minimum spanning tree has n-1 edges)
        if len(mst_edges_list) == len(adjacency_table_map) - 1:
            break

    return mst_edges_list, total_weight

# Example usage:
# Use adjacency_table to represent the graph
adjacency_table_map = {
    "A": {"B": 5, "C": 20, "D": 5, "E": 20, "F": 50},
    "B": {"A": 5, "C": 30, "D": 30},
    "C": {"A": 20, "B": 30, "F": 10},
    "D": {"A": 5, "B": 30, "E": 25},
    "E": {"A": 20, "D": 25, "F": 50, "G": 40},
    "F": {"A": 50, "C": 10, "E": 50, "G": 20},
    "G": {"E": 40, "F": 20}
}

# Call the Kruskal algorithm function
mst_edges, total_weight = kruskal(adjacency_table_map)

print("Minimum Spanning Tree Edges:", mst_edges)
print("Total Weight of the Minimum Spanning Tree:", total_weight)

The output is as follows:

The edge with the lowest weight selected this time : A-B, weight: 5. Add it to the tree.
The edge with the lowest weight selected this time : A-D, weight: 5. Add it to the tree.
The edge with the lowest weight selected this time : B-A, weight: 5. Discard it because it will form a cycle.
The edge with the lowest weight selected this time : D-A, weight: 5. Discard it because it will form a cycle.
The edge with the lowest weight selected this time : C-F, weight: 10. Add it to the tree.
The edge with the lowest weight selected this time : F-C, weight: 10. Discard it because it will form a cycle.
The edge with the lowest weight selected this time : A-C, weight: 20. Add it to the tree.
The edge with the lowest weight selected this time : A-E, weight: 20. Add it to the tree.
The edge with the lowest weight selected this time : C-A, weight: 20. Discard it because it will form a cycle.
The edge with the lowest weight selected this time : E-A, weight: 20. Discard it because it will form a cycle.
The edge with the lowest weight selected this time : F-G, weight: 20. Add it to the tree.
Minimum Spanning Tree Edges: [(5, 'A', 'B'), (5, 'A', 'D'), (10, 'C', 'F'), (20, 'A', 'C'), (20, 'A', 'E'), (20, 'F', 'G')]
Total Weight of the Minimum Spanning Tree: 80

Kruskal Algorithm steps

Example

Code

Reference Links