普里姆算法和克鲁斯卡尔算法

1. 最小生成树概述

最小生成树（Minimum Spanning Tree，简称为 MST）作为图论领域的关键概念，在加权连通图里有着广泛且重要的应用。在深入探究最小生成树的具体内涵之前，让我们先一同回顾图论中的一些基础知识点：

  • 加权图

    加权图（Weighted Graph）是一种每条边都被赋予一个权值（Weight）的图。这些权值可以代表距离、成本、时间等实际意义的度量。比如在一个表示城市间道路的图中，边的权值可以表示两个城市之间的距离。

  • 连通图

    连通图（Connected Graph）指的是在无向图中，任意两个顶点之间都存在路径相连。也就是说，从图中的任意一个顶点出发，都能够到达其他任何顶点。

  • 联通网

    带权连通图就是连通网。

  • 生成树

    生成树是一种特殊的连通子图，涵盖了连通图里的所有N个顶点，并且恰好包含N−1条边。

最小生成树这一概念，最初主要是为加权连通无向图量身打造的。不过，在有向图领域，也衍生出了与之类似的拓展性概念。而本课程所涉及的内容，主要围绕加权连通无向图来逐步展开，以此来探讨最小生成树相关知识。

对于一个加权连通无向图 G=(V,E)，其中V是图的顶点集合，E是图的边集合，每一条边 (u,v)∈E都有一个对应的权重w(u,v)。最小生成树是图G的一个子图，它满足以下条件：

  • 连通性：这个子图是连通的，也就是说对于图中任意两个顶点，都存在一条路径可以从一个顶点到达另一个顶点。
  • 包含所有顶点：子图包含了原图 G中的所有顶点 V。
  • 无环：子图中不包含任何回路（环），即不存在一条从某个顶点出发，经过若干条边后又回到该顶点的路径。
  • 最小权重：在所有满足上述三个条件的子图中，这个子图的所有边的权重之和是最小的。
image-20250322093915201

下面这四棵生成树均为连通子图，且每棵树都涵盖了图中的全部 6 个顶点，边数为 6 - 1 条。然而，它们所有边的权重总和并非最小，所以这三棵树并非该图的最小生成树。

在图论中，求最小生成树通常有两种经典方法，分别是克鲁斯卡尔（Kruskal）算法和普里姆（Prim）算法，接下来，我将为大家进行详细介绍。

2. 克鲁斯卡尔算法

克鲁斯卡尔（Kruskal）算法是一种贪心算法，它的核心思路是将图中所有的边按照权重从小到大进行排序，然后依次选取权重最小的边，只要加入这条边不会形成环，就将其纳入最小生成树的边集，直到最小生成树包含图中的所有顶点。

该算法的具体处理步骤如下：

  1. 排序边：把图中所有的边按照权重从小到大进行排序。
  2. 初始化并查集：为图中的每个顶点创建一个独立的集合，用于后续判断加入边时是否会形成环。
  3. 选择边：从排序好的边列表中依次选取边，如果该边连接的两个顶点不在同一个集合中（即加入这条边不会形成环），则将这条边加入最小生成树的边集，并将这两个顶点所在的集合合并。
  4. 重复步骤 3：不断重复步骤 3，直到最小生成树的边数达到顶点数减 1，此时就得到了图的最小生成树。

在判断加入一条边是否会形成环时，可以使用并查集。如果边的两个端点属于不同的集合，说明加入这条边不会形成环，将这两个集合合并；如果属于同一个集合，则跳过这条边。

首先我们要先把带权图的边结构定义出来：

1
2
3
4
5
6
7
8
9
struct Edge 
{
    int start, end, weight;
    bool operator<(const Edge& other) const 
    {
        return weight < other.weight;
    }
    Edge(int s, int e, int w) :start(s), end(e), weight(w) {}
};

结构体 Edge：包含起点 start、终点 end 和边的权重 weight。重载了小于运算符，方便对边按权重进行排序。

接着再把并查集类定义出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 并查集类
class UnionFind
{
public:
    UnionFind(int size);
    int find(int index);
    bool unite(int element1, int element2);
private:
    vector<int> m_parent;
    vector<int> m_rank;
};

UnionFind::UnionFind(int size)
{
    m_parent.resize(size);
    for (int i = 0; i < size; ++i)
    {
        m_parent[i] = i;
    }
    m_rank.resize(size, 0);
}

int UnionFind::find(int index)
{
    while (index != m_parent[index])
    {
        index = m_parent[index];
    }
    return index;
}

int UnionFind::rfind(int index)
{
    if (index != m_parent[index])
    {
        m_parent[index] = rfind(m_parent[index]);
    }
    return m_parent[index];
}

bool UnionFind::unite(int element1, int element2)
{
    if (element1 < 0 || element2 < 0 || element1 >= m_parent.size() || element2 >= m_parent.size())
    {
        return false;
    }
    int root1 = rfind(element1);
    int root2 = rfind(element2);
    if (root1 != root2)
    {
        if (m_rank[root1] < m_rank[root2])
        {
            m_parent[root1] = root2;
        }
        else if (m_rank[root1] > m_rank[root2])
        {
            m_parent[root2] = root1;
        }
        else
        {
            m_parent[root2] = root1;
            m_rank[root1]++;
        }
        return true;
    }
    return false;
}

最后就可以使用并查集来实现克鲁斯卡尔算法了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
vector<Edge> kruskal(int n, vector<Edge>& edges)
{
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    vector<Edge> mst; 
    for (const auto& edge : edges)
    {
        if (uf.unite(edge.start, edge.end))
        {
            mst.push_back(edge);
            if (mst.size() == n - 1)
            {
                break;
            }
        }
    }
    return mst;
}

void kruskalTest()
{
    int n = 6; 
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4},
        {3, 4, 7},  
        {4, 5, 3}, 
        {2, 5, 8}  
    };

    vector<Edge> mst = kruskal(n, edges);
    cout << "最小生成树的边：" << endl;
    for (const Edge& edge : mst)
    {
        cout << edge.start << " - " << edge.end << ", 权重: " << edge.weight << endl;
    }
}

int main() 
{
    kruskalTest();
    return 0;
}

kruskal 函数：

  • 首先对所有边按权重从小到大排序。
  • 初始化并查集。
  • 遍历排序后的边，对于每条边，如果加入这条边不会形成环（即两个端点不在同一个集合中），则将其加入最小生成树，并合并两个端点所在的集合。
  • 当最小生成树的边数达到 n - 1 时，停止循环。

测试程序的示例如如下：

image-20250322105920287

执行程序终端打印的结果是这样的:

1
2
3
4
5
6
最小生成树的边：
4 - 5, 权重: 3
2 - 3, 权重: 4
0 - 3, 权重: 5
3 - 4, 权重: 7
0 - 1, 权重: 10

克鲁斯卡尔算法的实现思路堪称并查集的经典应用案例，相关内容已多有探讨，这里便不再展开详述。若有小伙伴心存疑惑，请移步并查集

3. 普里姆算法

普里姆（Prim）算法同样是贪心算法，它从图中的任意一个顶点开始，每次选择与当前已加入最小生成树的顶点集合相连的边中权重最小的边，将对应的顶点加入到最小生成树的顶点集合中，直到所有顶点都被加入。

普利姆算法的处理步骤如下：

  1. 选择起始顶点：从图中任意选择一个顶点作为起始点，将其加入最小生成树的顶点集合。
  2. 选择最小边：在所有一个端点在最小生成树顶点集合中，另一个端点不在该集合中的边中，选择权重最小的边。
  3. 扩展生成树：将步骤 2 中选择的边加入最小生成树的边集，并将该边不在最小生成树顶点集合中的端点加入到该集合中。
  4. 重复步骤 2 和 3：不断重复步骤 2 和 3，直到最小生成树的顶点集合包含图中的所有顶点。

对应的 C++ 示例代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
vector<Edge> prim(int n, vector<vector<Edge>>& graph)
{
    vector<bool> visited(n, false);
    vector<Edge> mst;
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    visited[0] = true;
    for (const Edge& edge : graph[0])
    {
        pq.push({ edge.weight, {0, edge.end} });
    }

    while (!pq.empty()) 
    {
        int weight = pq.top().first;
        int from = pq.top().second.first;
        int to = pq.top().second.second;
        pq.pop();

        if (visited[to]) continue;

        visited[to] = true;
        mst.push_back({ from, to, weight});

        for (const Edge& edge : graph[to])
        {
            if (!visited[edge.end]) 
            {
                pq.push({ edge.weight, {to, edge.end} });
            }
        }
    }
    return mst;
}

void primTest()
{
    int n = 6; // 顶点数
    vector<vector<Edge>> graph;
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4},
        {3, 4, 7},
        {4, 5, 3},
        {2, 5, 8}
    };
    graph.resize(6);
    for (int i = 0; i < edges.size(); ++i)
    {
        int s = edges[i].start;
        int e = edges[i].end;
        int w = edges[i].weight;
        graph[s].push_back(Edge(s, e, w));
        graph[e].push_back(Edge(e, s, w));
    }

    vector<Edge> mst = prim(n, graph);
    cout << "最小生成树的边：" << endl;
    for (const auto& edge : mst) 
    {
        cout << edge.start << " - " << edge.end << ", 权重: " << edge.weight << endl;
    }
}

int main() 
{
    primTest();
    return 0;
}

示例代码终端打印的结果为:

1
2
3
4
5
6
最小生成树的边：
0 - 3, 权重: 5
3 - 2, 权重: 4
3 - 4, 权重: 7
4 - 5, 权重: 3
0 - 1, 权重: 10

关于示例代码定义的对象描述如下：

  • visited：一个布尔类型的向量，用于标记每个顶点是否已经被加入到最小生成树中，初始时所有顶点都未被访问。
  • mst：用于存储最小生成树中的边。
  • pq：一个优先队列（小顶堆），用于存储待处理的边。优先队列中的元素是一个三元组 {weight, {from, to}}，其中 weight 是边的权重，from 是边的起点，to 是边的终点。优先队列会根据边的权重进行排序，权重最小的边会排在队列的前面。

接着再给大家具体分析一下普里姆算法中边的选择过程：

  1. 初始化

    • 顶点数 n = 6，图使用邻接表 graph 表示。

    • 初始化所有顶点为未访问状态，visited 数组初始化为 {false, false, false, false, false, false}。

    • 选择顶点 0 作为起始顶点，将其标记为已访问，visited[0] = true。

    • 将与顶点 0 相连的边加入优先队列pq中：

      权重 边
      5 (0, 3)
      6 (0, 2)
      10 (0, 1)

  2. 步骤 1：选择边 (0, 3)

    • 从优先队列 pq 中取出权重最小的边 (0, 3)（权重为 5）。

    • 由于顶点 3 未被访问，将其标记为已访问，visited[3] = true。

    • 将边 (0, 3, 5) 加入最小生成树 mst 中。

    • 检查与顶点 3 相连且另一端顶点未被访问的边，将这些边加入优先队列 pq 中：

      权重 边
      4 (3, 2)
      6 (0, 2)
      7 (3, 4)
      10 (0, 1)
      15 (3, 1)

  3. 步骤 2：选择边 (2, 3)

    • 从优先队列 pq 中取出权重最小的边 (2, 3)（权重为 4）。

    • 由于顶点 2 未被访问，将其标记为已访问，visited[2] = true。

    • 将边 (2, 3, 4) 加入最小生成树 mst 中。

    • 检查与顶点 2 相连且另一端顶点未被访问的边，将这些边加入优先队列 pq 中：

      权重 边
      6 (0, 2)
      7 (3, 4)
      8 (2, 5)
      10 (0, 1)
      15 (3, 1)

  4. 步骤 3：选择边 (0, 2)

    • 从优先队列 pq 中取出权重最小的边 (0, 2)（权重为 6）。
    • 由于顶点 2 已经被访问过，跳过这条边。

    优先队列 pq 状态：

    权重 边
    7 (3, 4)
    8 (2, 5)
    10 (0, 1)
    15 (3, 1)

  5. 步骤 4：选择边 (3, 4)

    • 从优先队列 pq 中取出权重最小的边 (3, 4)（权重为 7）。

    • 由于顶点 4 未被访问，将其标记为已访问，visited[4] = true。

    • 将边 (3, 4, 7) 加入最小生成树 mst 中。

    • 检查与顶点 4 相连且另一端顶点未被访问的边，将这些边加入优先队列pq 中：

      权重 边
      3 (4, 5)
      8 (2, 5)
      10 (0, 1)
      15 (3, 1)

  6. 步骤 5，6：

    • 从优先队列 pq 中取出权重最小的边 (4, 5)（权重为 3）。
    • 由于顶点 5 未被访问，将其标记为已访问，visited[5] = true。
    • 将边 (4, 5, 3) 加入最小生成树 mst 中。
    • 从优先队列 pq 中取出权重最小的边 (2, 5)（权重为 8）。
    • 由于顶点 5 已经被访问过，跳过这条边。

    优先队列 pq 状态：

    权重 边
    10 (0, 1)
    15 (3, 1)

  7. 步骤 7：选择边 (0, 1)

    • 从优先队列 pq 中取出权重最小的边 (0, 1)（权重为 10）。
    • 由于顶点 1 未被访问，将其标记为已访问，visited[1] = true。
    • 将边 (0, 1, 10) 加入最小生成树 mst 中。
    • 从优先队列 pq 中取出权重最小的边 (3, 1)（权重为 15）。
    • 由于顶点 3 已经被访问过，跳过这条边。

    此时，所有顶点都已被访问，优先队列 pq 中所有数据均被弹出，最小生成树构建完成 mst 中的边为：

    • (0, 3, 5)
    • (2, 3, 4)
    • (3, 4, 7)
    • (4, 5, 3)
    • (0, 1, 10)

4. 总结

我们可以把数据结构中的图想象成一个城市交通网络，顶点就是城市，边就是连接城市的道路，边的权重就好比道路的建设成本，我们的目标是找到一种方案，用最小的成本让所有城市都能相互连通，这就是求最小生成树。

4.1 克鲁斯卡尔算法

  1. 克鲁斯卡尔算法原理

    克鲁斯卡尔算法就像是一个精打细算的道路规划者。他手上有一张所有道路（边）的清单，并且按照建设成本（权重）从低到高排好了序。他每次都从清单里挑出成本最低的道路，如果这条道路连接的两个城市还没有通过其他道路连通起来，他就会选择修建这条道路；要是这两个城市已经能通过其他道路互相到达了，那这条道路就不建了。一直重复这个过程，直到所有城市都连通。

  2. 克鲁斯卡尔算法适合稀疏图

    稀疏图就像是地广人稀地区的城市网络，城市（顶点）数量不少，但连接城市的道路（边）没那么多。在这种情况下，道路清单（边的集合）不会很长，排序和挑选道路的工作量都不会太大。所以克鲁斯卡尔算法在稀疏图里能比较高效地找到成本最低的道路建设方案，也就是最小生成树。

4.2 普里姆算法

  1. 普里姆算法原理

    普里姆算法则像是从一个中心城市开始扩张的建设者。他先选一个城市作为起点，然后看看从这个城市出发，哪条道路的建设成本最低，就先修建这条道路，把新的城市纳入到已经连通的城市网络里。接着，他再从已经连通的这些城市出发，继续找成本最低的道路去修建，不断扩大连通范围，直到所有城市都被连起来。

  2. 普里姆算法适合稠密图

    稠密图就像是繁华都市里的城市网络，城市之间的道路密密麻麻。在这种情况下，我们更关心从已经连通的城市集合出发，去连接其他城市的道路成本。普里姆算法从一个点开始不断扩展，每次只关注与已连通部分相连的道路，就很适合这种情况。而且在稠密图里，使用合适的数据结构可以更方便地找到成本最低的道路，整体效率会比较高。如果用克鲁斯卡尔算法，面对密密麻麻的道路清单，排序和处理的工作量就会变得很大。

综上所述，克鲁斯卡尔算法在道路少的稀疏图里表现出色，而普里姆算法在道路密集的稠密图中更能发挥优势。