python 算法之 克鲁斯卡尔算法

原理

克鲁斯卡尔（Kruskal）算法是一种用于求解最小生成树（Minimum Spanning Tree，MST）的贪心算法。最小生成树是一个连通加权无向图中生成树（即包含图中所有顶点并且是一棵树），其所有边的权值之和最小。

克鲁斯卡尔算法的基本思想是从图中所有边中选择权值最小的边，并且保证选择的边不构成环路，直到选取了 n-1 条边为止（n 是顶点的数量）。这样得到的就是最小生成树。

下面是克鲁斯卡尔算法的详细步骤：

1. 将图中的所有边按照权值进行升序排序。
2. 初始化一个空的最小生成树 MST。
3. 依次遍历排序后的边，每次取出权值最小的边。
4. 判断当前取出的边是否会形成环路。若不会形成环路，则将该边加入到最小生成树 MST 中。
5. 重复步骤 4，直到最小生成树 MST 中包含了 n-1 条边，其中 n 是图的顶点数量。

代码实现

def kruskal(graph):
    # 将图中的边按权值排序
    graph = sorted((w, u, v) for u, nbrs in enumerate(graph) for v, w in nbrs)
    mst = []  # 存储最小生成树的边
    parent = list(range(len(graph)))  # 并查集初始化，每个节点的父节点是自己

    # 并查集的查找操作，找到根节点
    def find(u):
        if u != parent[u]:
            parent[u] = find(parent[u])
        return parent[u]

    # 遍历排序后的边
    for w, u, v in graph:
        pu, pv = find(u), find(v)
        if pu != pv:  # 如果两个顶点不在同一个连通分量中，即不会形成环路
            mst.append((u, v, w))  # 将该边加入最小生成树
            parent[pv] = pu  # 合并两个连通分量

    return mst

# 示例输入
graph = [
    [(5, 1), (3, 2)],
    [(5, 0), (6, 2), (2, 3)],
    [(3, 0), (6, 1), (7, 3), (9, 4)],
    [(2, 1), (7, 2), (4, 4)],
    [(9, 2), (4, 3)]
]

# 计算最小生成树
mst = kruskal(graph)
print("最小生成树：", mst)

介绍代码的功能和实现原理：

1. kruskal() 函数接受一个图 graph 作为输入，并返回该图的最小生成树。
2. 首先，将图中的边按照权值进行排序，这可以通过列表推导式来完成。每条边表示为元组 (w, u, v)，其中 w 是边的权值，u 和 v 是边所连接的两个顶点的索引。
3. 初始化一个空列表 mst，用于存储最小生成树的边。
4. 初始化一个列表 parent，其中的每个元素表示一个节点的父节点，最初都指向自己。这个列表将用于实现并查集。
5. 定义了一个内部函数 find(u)，用于查找节点 u 所在连通分量的根节点。这个函数使用路径压缩技术，可以快速找到根节点，并且在查找过程中将路径上的节点直接连接到根节点，以减少后续查找的时间。
6. 遍历排序后的边，对每一条边 (w, u, v) 进行处理。
7. 对于每条边，使用 find() 函数查找其两个顶点 u 和 v 所在连通分量的根节点 pu 和 pv。
8. 如果 pu 和 pv 不相等，说明 u 和 v 不在同一个连通分量中，加入这条边不会形成环路，因此将其加入最小生成树 mst 中，并将这两个连通分量合并。合并操作通过将 pv 的父节点指向 pu 来完成。
9. 最后，返回最小生成树 mst。

这就是代码的主要功能和实现原理。它使用了克鲁斯卡尔算法来寻找最小生成树，通过并查集来维护连通分量，确保在构建最小生成树的过程中不会形成环路。