How to implement Kruskal's algorithm using Python?

How to implement Kruskal's algorithm using Python?

Introduction:
Kruskal's algorithm is a classic algorithm for solving the minimum spanning tree, which can find the spanning tree with the minimum total weight in a given weighted connected graph. This article will introduce how to implement Kruskal's algorithm using Python and provide detailed code examples.

1. Algorithm introduction:
   The basic idea of ​​Kruskal's algorithm is to sort all the edges in the connected graph according to their weights, and then select the edges from small to large. If the current edge selected is not If a loop is formed, it is added to the minimum spanning tree and marked as visited. Until the number of edges in the minimum spanning tree is equal to the number of vertices in the graph minus one.
2. Implementation steps:
   (1) Define the class of the graph and initialize the number of vertices and edges of the graph.
   (2) Define the class of each edge and initialize the starting point, end point and weight of the edge.
   (3) Write a function to implement and initialize the set, including finding the root node and merging sets.
   (4) Write the main function to implement Kruskal's algorithm, including sorting edges, selecting edges one by one to determine whether they form a cycle, adding edges to the minimum spanning tree, and calculating the total weight of the minimum spanning tree.
3. Code example:

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数
        self.graph = []

    # 添加边
    def add_edge(self, u, v, weight):
        self.graph.append([u, v, weight])

    # 查找根节点
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    # 合并集合
    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    # 克鲁斯卡尔算法
    def kruskal_algorithm(self):
        result = []
        i = 0
        e = 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, weight = self.graph[i]
            i += 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e += 1
                result.append([u, v, weight])
                self.union(parent, rank, x, y)

        # 打印最小生成树
        print("最小生成树：")
        for u, v, weight in result:
            print(f"{u} -- {v}     {weight}")

        # 计算最小生成树的总权值
        total_weight = sum(weight for u, v, weight in result)
        print("最小生成树的总权值：", total_weight)


if __name__ == '__main__':
    g = Graph(6)
    g.add_edge(0, 1, 4)
    g.add_edge(0, 2, 3)
    g.add_edge(1, 2, 1)
    g.add_edge(1, 3, 2)
    g.add_edge(2, 3, 4)
    g.add_edge(2, 4, 3)
    g.add_edge(3, 4, 2)
    g.add_edge(3, 5, 1)
    g.add_edge(4, 5, 6)

    g.kruskal_algorithm()

4. Result analysis:
   The above code is a typical example, which constructs a weighted undirected graph containing 6 vertices. And use Kruskal's algorithm to solve its minimum spanning tree. The program prints the edges in the minimum spanning tree and the total weight of the minimum spanning tree.

Conclusion:
Kruskal's algorithm is an efficient method for solving the minimum spanning tree of a connected graph. By sorting the edges and merging the sets, you can get a minimum spanning tree with the minimum total Spanning tree of weights. Using Python to implement Kruskal's algorithm can help us better understand the principles and processes of the algorithm, and easily apply it to practical problems.

The above is the detailed content of How to implement Kruskal's algorithm using Python?. For more information, please follow other related articles on the PHP Chinese website!