图论中的最小生成树算法：Kruskal算法详解与实现

图论中的最小生成树算法：Kruskal算法详解与实现

引用

CSDN

1.

https://blog.csdn.net/m0_49844155/article/details/146488052

最小生成树算法是图论中的一个重要概念，广泛应用于网络设计、电路布线等领域。本文将详细介绍Kruskal算法，一种基于边的最小生成树算法，并通过具体示例和代码实现帮助读者深入理解。

Kruskal算法简介

Kruskal算法用于求解图的最小生成树问题。与Prim算法不同，Kruskal算法是通过维护边的集合来实现的。其基本思路如下：

1. 将图中的所有边按照权值从小到大排序
2. 依次遍历排序后的边
3. 如果边的两个端点不在同一个集合中，则将这条边加入最小生成树，并将两个端点所在的集合合并
4. 重复步骤3，直到最小生成树包含所有节点

算法步骤详解

以一个具体的图为例，说明Kruskal算法的工作过程：

1. 首先将图中的边按照权值从小到大排序：[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]
2. 依次遍历排序后的边：

• 选边(1,2)，节点1 和 节点2 不在同一个集合，所以生成树可以添加边(1,2)，并将 节点1，节点2 放在同一个集合。
• 选边(4,5)，节点4 和 节点 5 不在同一个集合，生成树可以添加边(4,5) ，并将节点4，节点5 放到同一个集合。
• 选边(1,3)，节点1 和 节点3 不在同一个集合，生成树添加边(1,3)，并将节点1，节点3 放到同一个集合。
• 选边(2,6)，节点2 和 节点6 不在同一个集合，生成树添加边(2,6)，并将节点2，节点6 放到同一个集合。
• 选边(3,4)，节点3 和 节点4 不在同一个集合，生成树添加边(3,4)，并将节点3，节点4 放到同一个集合。
• 选边(6,7)，节点6 和 节点7 不在同一个集合，生成树添加边(6,7)，并将 节点6，节点7 放到同一个集合。
• 选边(5,7)，节点5 和 节点7 在同一个集合，不做计算。
• 选边(1,5)，两个节点在同一个集合，不做计算。
• 后面遍历 边(3,2)，(2,4)，(5,6) 同理，都因两个节点已经在同一集合，不做计算。

最终生成的最小生成树如下：

并查集的应用

在Kruskal算法中，需要判断两个节点是否在同一个集合，以及将两个节点加入同一个集合。这正是并查集的主要功能：

• 将两个元素添加到一个集合中
• 判断两个元素在不在同一个集合

因此，在实现Kruskal算法时，通常会使用并查集来管理节点的集合关系。

代码实现

以下是Kruskal算法的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// l,r为 边两边的节点，val为边的数值
struct Edge {
    int l, r, val;
};
// 节点数量
int n = 10001;
// 并查集标记节点关系的数组
vector<int> father(n, -1); // 节点编号是从1开始的，n要大一些
// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集的查找操作
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}
// 并查集的加入集合
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}
int main() {
    int v, e;
    int v1, v2, val;
    vector<Edge> edges;
    int result_val = 0;
    cin >> v >> e;
    while (e--) {
        cin >> v1 >> v2 >> val;
        edges.push_back({v1, v2, val});
    }
    // 执行Kruskal算法
    // 按边的权值对边进行从小到大排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
    });
    // 并查集初始化
    init();
    // 从头开始遍历边
    for (Edge edge : edges) {
        // 并查集，搜出两个节点的祖先
        int x = find(edge.l);
        int y = find(edge.r);
        // 如果祖先不同，则不在同一个集合
        if (x != y) {
            result_val += edge.val; // 这条边可以作为生成树的边
            join(x, y); // 两个节点加入到同一个集合
        }
    }
    cout << result_val << endl;
    return 0;
}

以下是Kruskal算法的Python实现：

import sys
# 边的数据结构
class Edge():
    def __init__(self, s, t, val):
        self.s = s # 边起点
        self.t = t # 边终点
        self.val = val # 边权值
# 并查集
class unionFind():
    def __init__(self, n):
        self.n = n # 结点总个数
        self.father = list(range(v + 1)) # 子->父结点映射，这个里的结点是节点编号如edge.s，不是Edge的实例！
    def find(self, u):
        if u != self.father[u]:
            self.father[u] = self.find(self.father[u])
        return self.father[u]
    def isSame(self, u, v):
        return self.find(u) == self.find(v)
    def join(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            self.father[root_v] = root_u
if __name__ == '__main__':
    lines = sys.stdin.readlines()
    v, e = map(int, lines[0].strip().split()) # 定点数v，边数e
    # 创建边集合
    edges = []
    for i in range(1, len(lines)):
        # 边起点，边终点，边权值
        s, t, val = map(int, lines[i].strip().split())
        edges.append(Edge(s, t, val))
    # 按照边权值升序排序edges
    edges.sort(key=lambda edge: edge.val) 
    # 创建并查集，从最小边权值开始遍历边：每条边
    # 如果两端点非同根（不都在并查集中），则说明当前边加入之后不会成环，直接加入生成树即可；
    # 如果两端点同根，说明当前边加入之后会成环，不能入树
    ans = 0 # 记录最小权值（最短距离）路径的权值和（距离和）
    uf = unionFind(v) # 创建并查集
    for edge in edges:
        # 非同根情况才需要操作，同根时直接跳过
        if not uf.isSame(edge.s, edge.t):
            uf.join(edge.s, edge.t)
            ans += edge.val
    print(ans)

拓展应用

输出最小生成树的边

如果需要输出最小生成树的边，可以在判断两个节点不在同一个集合时，将这条边保存下来：

vector<Edge> result; // 存储最小生成树的边
// 如果祖先不同，则不在同一个集合
if (x != y) {
    result.push_back(edge); // 记录最小生成树的边
    result_val += edge.val; // 这条边可以作为生成树的边
    join(x, y); // 两个节点加入到同一个集合
}

算法选择策略

Kruskal算法和Prim算法各有优劣：

• Kruskal算法：适用于边较少的稀疏图，时间复杂度为O(nlogn)，其中n为边的数量。
• Prim算法：适用于节点较少的稠密图，时间复杂度为O(n^2)，其中n为节点数量。

因此，在选择算法时，需要根据图的特性来决定：

• 如果图中节点多但边少，使用Kruskal算法更优。
• 如果图中节点少但边多，使用Prim算法更优。