Python coding test course, minimum spanning tree

1. What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) is a subgraph of a connected graph that includes all vertices while minimizing the sum of the weights of the edges. In other words, the Minimum Spanning Tree is the process of finding a tree that connects all vertices in the given graph with the least total cost while avoiding cycles.

2. Problem Description

The following is the Minimum Spanning Tree problem:

Given n cities and m roads, find the minimum cost to connect all the cities with roads.

Input format: The first line contains two integers n (the number of cities) and m (the number of roads). The next m lines contain three integers a, b, c representing that the cost of the road connecting city a and city b is c.

3. Approach

To solve the Minimum Spanning Tree problem, two algorithms are commonly used:

• Prim’s Algorithm
• Kruskal’s Algorithm

In this article, we will use Kruskal’s algorithm to solve the problem.

3.1 Kruskal’s Algorithm

Kruskal’s algorithm proceeds in the following steps:

1. Sort all the edges in ascending order by weight (cost).
2. Starting from the smallest edge, select it. If the selected edge does not form a cycle, include it in the MST.
3. Repeat step 2 until all edges have been examined.

4. Algorithm Implementation

Now, let’s start implementing Kruskal’s algorithm in Python to solve the above problem.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
    

4.1 Input and Edge Sorting

We will take the number of cities and road information as input, and sort the edges by weight.

import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    edges = []

    for _ in range(m):
        a, b, c = map(int, input().split())
        edges.append((c, a, b))

    edges.sort()  # Sort by ascending weight
    

4.2 Applying Kruskal's Algorithm

We examine the sorted edges one by one to construct the MST.

    ds = DisjointSet(n)
    mst_cost = 0

    for cost, a, b in edges:
        if ds.find(a) != ds.find(b):  # Check for cycles
            ds.union(a, b)
            mst_cost += cost

    print(mst_cost)  # Output the minimum spanning tree cost
if __name__ == "__main__":
    main()
    

5. Conclusion

In this article, we explored the concept of the Minimum Spanning Tree and how to solve the problem using Kruskal's algorithm. I hope you can develop the ability to analyze and solve given problems in your own way.