博客

浅谈算法之最小生成树Kruskal的Python实现

  • Post category:Python

让我来为你详细讲解“浅谈算法之最小生成树Kruskal的Python实现”的完整攻略。

最小生成树Kruskal算法

最小生成树是一个图论中的问题。 一个无向图的最小生成树是指一个连通子图，它含有原图中所有的n个顶点，但只有最少数量的边使得子图连通。Kruskal算法是一个构造所有节点的最小生成树的算法，它以边为基础而不是点。

算法描述：

  • 创建一个空的最小生成树集合，初始时这个集合为空。
  • 对所有的边进行排序，并且依次考虑每一条边。
  • 如果边的两个端点在最小生成树集合中已经存在同一个集合中，则把这条边抛弃。
  • 否则加入当前边到最小生成树集合中，并把该边的两个端点所在的集合合并成同一个集合。

Python实现

下面是Kruskal算法的Python实现： 

class WeightedGraph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, start, end, weight):
        self.graph.append((start, end, weight))

    def find_parent(self, parent, node):
        if parent[node] == node:
            return node
        return self.find_parent(parent, parent[node])

    def union(self, parent, rank, x, y):
        xroot = self.find_parent(parent, x)
        yroot = self.find_parent(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

    def kruskal(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:
            start, end, weight = self.graph[i]
            i += 1

            x = self.find_parent(parent, start)
            y = self.find_parent(parent, end)

            if x != y:
                e += 1
                result.append((start, end, weight))
                self.union(parent, rank, x, y)

        print("Edges of minimum spanning tree")
        for start, end, weight in result:
            print("%d - %d: %d" % (start, end, weight))

上述代码中，WeightedGraph是一个加权无向图的类，包括V个顶点和E条边。kruskal是一个函数，它返回一组边，这些边构成图的最小生成树。首先按权重对所有边进行排序，并为每个节点创建一个父节点和一个秩。将遍历按排序顺序的边，如果边的两个端点分别在不同的父节点中，则将它们合并成一个集合(即将两个集合共同连接)，同时将该边添加到result列表中。

示例

为了更好的理解Python实现的Kruskal算法，下面提供两个示例说明。

示例1

假设以下有一个无向加权图：

该图有6个节点和8条边，我们可以使用Kruskal算法找出一组边，它们构成了最小生成树。调用kruskal函数，在Python控制台中输入：

graph = WeightedGraph(6)
graph.add_edge(0, 1, 4)
graph.add_edge(0, 2, 4)
graph.add_edge(1, 2, 2)
graph.add_edge(1, 3, 6)
graph.add_edge(2, 3, 8)
graph.add_edge(2, 4, 9)
graph.add_edge(3, 4, 10)
graph.add_edge(3, 5, 12)

graph.kruskal()

运行结果：

Edges of minimum spanning tree
1 - 2: 2
0 - 1: 4
1 - 3: 6
2 - 4: 9
3 - 5: 12

结果告诉我们，最小生成树由每个端点之间的最短路径组成，这里有5条边。

示例2

假设以下有一个无向加权图：

该图有6个节点和9条边，我们可以使用Kruskal算法找出一组边，它们构成了最小生成树。调用kruskal函数，在Python控制台中输入：

graph = WeightedGraph(6)
graph.add_edge(0, 1, 1)
graph.add_edge(0, 2, 3)
graph.add_edge(0, 3, 4)
graph.add_edge(1, 2, 2)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 6)
graph.add_edge(2, 4, 7)
graph.add_edge(3, 4, 8)
graph.add_edge(3, 5, 9)

graph.kruskal()

运行结果：

Edges of minimum spanning tree
0 - 1: 1
1 - 2: 2
0 - 3: 4
3 - 4: 8
3 - 5: 9

结果告诉我们，最小生成树由每个端点之间的最短路径组成，这里有5条边。

以上就是Kruskal算法的Python实现和两个示例的详细说明，希望对你有所帮助。

Tags: ,