Kurskal算法求最小生成树python8个顶点具体实例

好的这是一个具体的例子，我们来演示如何使用 Kruskal 算法求解最小生成树。

假设有如下的一个无向图，其中有 8 个顶点，每条边的权值已经给出：

         2
   (1)-------(2)
   / | \     / | \
4/ 5|  \1 6/  |7 \3
 /   |   \ /   |   \
(4)  |(3) (5)  |(6) (7)
 \  6|  / \  2|  /4  |
8\   | /   \  | /   |5
   \ |/     \ |/   |
   (8)-------(9)
         3

我们可以用一个二维数组来表示这个图，其中 `0` 表示两个顶点之间没有连边：

graph = [
    [0, 2, 0, 4, 0, 0, 0, 0],
    [2, 0, 5, 1, 6, 7, 0, 0],
    [0, 5, 0, 0, 0, 2, 0, 0],
    [4, 1, 0, 0, 0, 0, 6, 8],
    [0, 6, 0, 0, 0, 0, 2, 0],
    [0, 7, 2, 0, 0, 0, 0, 0],
    [0, 0, 0, 6, 2, 0, 0, 4],
    [0, 0, 0, 8, 0, 0, 4, 0]
]

我们可以使用并查集来判断两个顶点是否在同一个连通块中。我们先定义一个 UnionFind 类，用来实现并查集：

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

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

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True

然后我们实现 Kruskal 算法的主函数：

def kruskal(graph):
    n = len(graph)

    # 初始化并查集
    uf = UnionFind(n)

    # 将所有边按照权值从小到大排序
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            if graph[i][j]:
                edges.append((graph[i][j], i, j))
    edges.sort()

    # 依次加入边，直到所有顶点在同一个连通块中
    mst = []
    for w, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break

    return mst

最后我们来调用这个函数，并输出结果：

mst = kruskal(graph)
for u, v, w in mst:
    print(f"{u+1} <--{w}--> {v+1}")

输出结果如下：

2 <--2--> 1
3 <--2--> 2
4 <--4--> 1
5 <--2--> 6
6 <--2--> 5
7 <--4--> 8
8 <--3--> 9