本文最后更新于：2026年2月22日晚上

0x00.绪论

Kruskal 算法与 Prim 算法 是较为常用的用来 查找最小生成树 的算法，刚好今天上离散数学课的时候讲到了最小生成树，所以作为一名蒟蒻前·OIer 咱今天也来简单讲讲 ~~重新复习~~ 这都是些个什么东西 XD （又想起了当年高中图论学不好赛场上被暴打的惨痛经历…）

0x01 生成树&最小生成树

在正式讲解这两个算法之前我们先来看看什么是生成树和最小生成树，众所周知我们一张 连通的无向图 一般有很多条边连着很多个顶点，从任意一点出发都有路径达到另一个点， 生成树 （Spanning Tree）即为 具有该连通无向图所有顶点的树形连通子图 ，一棵生成树必须满足如下特性：

是树（即不存在环）
包含原图的所有顶点
边的数量为 顶点数 - 1

由此我们不难得到以下扩展结论：

一张连通的无向图可以有多个生成树，但是他们的顶点与边的数量都固定相同
移除任意一条边都会破坏生成树的连通性
在生成树中添加一条边会形成环

而 最小生成树 （Minimum Spanning Tree）针对的便是 边带有权值 的情况：当一棵生成树有着最小的权值和时，我们便称之为最小生成树，类似地我们有如下特性：

一张连通图中可能有多个最小生成树（在所有边权值相等的极端情况下，该图的所有生成树都是最小生成树）
如果图中每一条边的权值都互不相同，则 最小生成树唯一

最小生成树有很多可以应用的地方，例如电网的路径规划等

图的几种表示方法我们已经在【ALGORITHM.0x02】Dijkstra 算法浅析当中进行叙述，这里不再赘述

0x02. Kruskal 算法

既然最小生成树在现实生活中是非常有用的（？），因此我们自然需要想办法求解一张图当中的最小生成树，一个比较常用的算法是由美国数学家 Joseph Bernard Kruskal 在 1956 年发表的 Kruskal 算法，该算法以边为核心使用 贪心策略 进行最小生成树的产生，具体而言：

首先创建一份与原图相同的无边副本（拷贝原图点集）
将原图中的所有边的权值从小到大排序
从最小边开始进行遍历，若该边的两个点不在同一连通分量中（在新图中两点尚不连通），则添加该边到新图中
重复遍历过程，直到选够 n - 1 条边

在算法的中间过程中，可能会创建很多不连通的子连通分量，之后这些子连通分量再进行连接，因此需要注意的是， 如果图不连通，则 Kruskal 只能得到最小生成森林

下面这张来自 Wikipedia 的 GIF 很好地演示了 Kruskal 算法的基本过程：

在实现细节上，对于连通分量的判断，我们其实很容易想到可以使用并查集进行实现——将每个点初始化为独立集合，之后在不断连接的过程中合并即可

以下是一个非常朴素的 Kruskal 的例子，我们假设输入和输出都是无向图的邻接表表示（即对于一条 u、v之间的边，我们在输入和输出的图里都存在 u->v 和 v->u 两条边）：

#include <algorithm>
#include <numeric>
#include <vector>
#include <tuple>
#include <utility>
#include <queue>

typedef std::tuple<int, int, int> Edge; // start, end, weight
struct EdgeCmp {
    bool operator()(Edge const& a, Edge const& b) const {
        return std::get<2>(a) > std::get<2>(b); // min-heap
    }
};

typedef std::pair<int, int> EdgeOut; // end, weight
typedef std::vector<std::vector<EdgeOut>> Graph; // adjunct list

Graph kruskal(Graph &g, int node_nr)
{
    Graph res(node_nr);
    std::vector<int> rels(node_nr);
    std::priority_queue<Edge, vector<Edge>, EdgeCmp> min_heap;

    /* init for disjoint set */
    std::iota(rels.begin(), rels.end(), 0);
    auto find_x = [&](int x) -> int {
        std::vector<int> path;

        while (rels[x] != x) {
            path.push_back(x);
            x = rels[x];
        }
        
        for (int n : path) {
            rels[n] = x;
        }
        
        return x;
    };
    auto union_set = [&](int x, int y) -> void {
        rels[find_x(x)] = find_x(y);
    };
    
	/* sort edges by weight */
    for (int i = 0; i < g.size(); i++) {
        for (int j = 0; j < g[i].size(); j++) {
            if (i <  g[i][j].first) {
                min_heap.push({i, g[i][j].first, g[i][j].second});
            }
            // we don't need this, in fact
            //min_heap.push({g[i][j].first, i, g[i][j].second});
        }
    }
    
    /* add nodes by edges until n - 1 edges */
	int edge_added = 0;
    while (((node_nr - 1) != edge_added) && (!min_heap.empty())) {
        Edge min_edge = min_heap.top();
        min_heap.pop();
        
        int start = std::get<0>(min_edge);
        int end = std::get<1>(min_edge);
        
        int rs = find_x(start);
        int re = find_x(end);
        if (rs != re) {
            union_set(rs, re);
            res[start].push_back({end, std::get<2>(min_edge)});
            res[end].push_back({start, std::get<2>(min_edge)});
            edge_added++;
        }
    }
    
    return res;
}

实际上对于 Kruskal 而言，我们使用 朴素边表示 更加适合，因为邻接表更适用于有向图，而我们的 Kruskal 算法仅适用于无向图，这会导致很多额外的数据处理过程

以下是一个朴素的使用朴素边表示的 Kruskal 算法示例，更加简洁：

#include <algorithm>
#include <numeric>
#include <vector>
#include <tuple>
#include <utility>
#include <queue>

typedef std::tuple<int, int, int> Edge; // node1, node2, weight
struct EdgeCmpAscending {
    bool operator()(Edge const& a, Edge const& b) const {
        return std::get<2>(a) < std::get<2>(b);
    }
};
typedef std::vector<Edge> Graph;

Graph kruskal(Graph &g_src, int node_nr)
{
    /* kruskal variables */
    Graph res;
    int edge_added = 0;
    std::vector<Edge> edges;

    /* disjoint set */
    std::vector<int> rels(node_nr);
    std::iota(rels.begin(), rels.end(), 0);
    auto find_x = [&](int x) -> int {
        while (rels[x] != x) {
            rels[x] = rels[rels[x]];
            x = rels[x];
        }
        
        return x;
    };
    auto unite_xy = [&](int x, int y) -> void {
        int rx = find_x(x);
        int ry = find_x(y);
        rels[rx] = ry;
    };
    
    /* start kruskal */
    for (Edge &edge : g_src) {
        edges.push_back(edge);
    }
    
    sort(edges.begin(), edges.end(), EdgeCmpAscending{});
    
    for (int i = 0; i < edges.size() && ((node_nr - 1) != edge_added); i++) {
        const Edge &edge = edges[i];
        int u = std::get<0>(edge);
        int v = std::get<1>(edge);
        int w = std::get<2>(edge);

        int ru = find_x(u);
        int rv = find_x(v);
        if (ru != rv) {
            unite_xy(ru, rv);
            res.push_back(edge);
            edge_added++;
        }
    }

    return res;
}

例题：洛谷 - P3366 【模板】最小生成树

题目就不抄了，简而言之非常朴素的 Kruskal 算法，输入是图，要求我们在有最小生成树时输出边权值和，没有则输出 No，什么情况下会无法创建最小生成树？答案是在我们遍历完所有边之后，加入到新图的边的数量不为 n-1 的时候，说明我们只成功创建了最小生成森林

这里我们直接把上面的 Kruskal 代码简单改改即可，这里注意点标号从 1 开始：

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <tuple>
#include <utility>
#include <queue>

using namespace std;

typedef std::tuple<int, int, int> Edge; // node1, node2, weight
struct EdgeCmpAscending {
    bool operator()(Edge const& a, Edge const& b) const {
        return std::get<2>(a) < std::get<2>(b);
    }
};
typedef std::vector<Edge> Graph;

long long kruskal(Graph &g_src, int node_nr)
{
    /* kruskal variables */
    Graph g_res;
    long long res = 0;
    int edge_added = 0;
    std::vector<Edge> edges;

    /* disjoint set */
    std::vector<int> rels(node_nr + 1);
    std::iota(rels.begin(), rels.end(), 0);
    auto find_x = [&](int x) -> int {
        while (rels[x] != x) {
            rels[x] = rels[rels[x]];
            x = rels[x];
        }
        
        return x;
    };
    auto unite_xy = [&](int x, int y) -> void {
        int rx = find_x(x);
        int ry = find_x(y);
        rels[rx] = ry;
    };
    
    /* start kruskal */
    for (Edge &edge : g_src) {
        edges.push_back(edge);
    }
    
    sort(edges.begin(), edges.end(), EdgeCmpAscending{});
    
    for (int i = 0; i < edges.size() && ((node_nr - 1) != edge_added); i++) {
        const Edge &edge = edges[i];
        int u = std::get<0>(edge);
        int v = std::get<1>(edge);
        int w = std::get<2>(edge);

        int ru = find_x(u);
        int rv = find_x(v);
        if (ru != rv) {
            unite_xy(ru, rv);
            g_res.push_back(edge);
            edge_added++;
            res += w;
        }
    }

    return edge_added == (node_nr - 1) ? res : -1;
}

int main(int argc, char **argv, char **envp)
{
    int m, n;

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> m >> n;

    Graph g;

    for (int i = 0; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.push_back({u, v, w});
    }

    long long res = kruskal(g, m);
    if (res != -1) {
        cout << res << endl;
    } else {
        cout << "orz" << endl;
    }

    return 0;
}

直接 AC，不过应该没什么 hack 数据， ~~这个 Kruskal 的写法也不怎么优雅~~ ：

0x03. Prim 算法

不同于 Kruskal 算法以边作为核心，Prim 算法建立最小生成树的方法是以点作为核心使用 贪心策略 进行最小生成树的产生，具体而言：

创建空点集 V 与空边集 E，选取任一点为起始点添加到 V 中
不断进行如下操作，直至点集 V 与原图点集相同：
- 在原图边集合中选取权值最小的边 (u, v) ，其中 u 为 V 中元素而 v 为未加入 V 的元素
- 将 v 加入 V ，将 (u, v) 加入 E

我们不难看出，Prim 算法基于点为核心的特性，使其适合使用邻接表来完成算法过程，以下是一个朴素的基于邻接表的 Prim 算法实现：

#include <vector>
#include <utility>
#include <climits>
#include <set>

typedef std::pair<int, int> EdgeOut;
typedef std::vector<std::vector<EdgeOut>> Graph;

Graph prim(const Graph &g_src, int node_nr)
{
    std::set<int> pset;
    Graph g_res(node_nr);

    int start = 0; // or any, whatever
    pset.insert(start);
    
    while (pset.size() < node_nr) {
        int u, v, w = INT_MAX;

        for (int i = 0; i < g_src.size(); i++) {
            if (pset.find(i) == pset.end()) {
                continue;
            }

            for (int j = 0; j < g_src[i].size(); j++) {
                if (pset.find(g_src[i][j].first) != pset.end()) {
                    continue;
                }

                if (g_src[i][j].second < w) {
                    u = i;
                    v = g_src[i][j].first;
                    w = g_src[i][j].second;
                }
            }
        }

        if (w == INT_MAX) { // nothing to do
            break;
        }
        
        pset.insert(v);
        g_res[u].push_back({v, w});
        g_res[v].push_back({u, w});
    }

    return g_res;
}

例题：洛谷 - P3366 【模板】最小生成树

和之前是同一题，不同的是这次我们使用 Prim 算法而非 Kruskal 算法进行最小生成树的求解，直接将上面的模板改一改即可：

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <set>
#include <tuple>

typedef std::tuple<int, int, long long> Edge;
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut>> Graph;

long long prim(const Graph &g_src, int node_nr)
{
    std::set<int> pset;
    Graph g_res(node_nr + 1);
    long long res = 0;

    int start = 1; // or any, whatever
    pset.insert(start);
    
    while (pset.size() < node_nr) {
        int u, v;
        long long w = LLONG_MAX;

        for (int i = 1; i<= node_nr; i++) {
            if (pset.find(i) == pset.end()) {
                continue;
            }

            for (int j = 0; j < g_src[i].size(); j++) {
                if (pset.find(g_src[i][j].first) != pset.end()) {
                    continue;
                }

                if (g_src[i][j].second < w) {
                    u = i;
                    v = g_src[i][j].first;
                    w = g_src[i][j].second;
                }
            }
        }

        if (w == LLONG_MAX) { // nothing to do
            break;
        }
        
        pset.insert(v);
        g_res[u].push_back({v, w});
        g_res[v].push_back({u, w});
        res += w;
    }

    return pset.size() == node_nr ? res : -1;
}

int main(int argc, char **argv, char **envp)
{
    int n, m;

    std::cin >> n >> m;
    Graph g(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    long long res = prim(g, n);
    if (res != -1) {
        std::cout << res << std::endl;
    } else {
        std::cout << "orz" << std::endl;
    }

    return 0;
}

——你以为直接过了？Too young too simpe！Sometimes naive！我们会发现有三个点 TLE 了：

优化：堆优化

和前面的朴素 Dijkstra 算法一样，我们发现在我们的朴素 Prim 算法实现当中有一些可以优化的点：

对于最小边的选取是一个双重循环，这直接把时间复杂度拉满了，因此我们不难想到类似的优化方法——使用二叉堆优化最小边的查找过程，同时在每次新加入一个点时将其边加入到二叉堆中即可
std::set 的成本其实并不低，实际上我们要标识某个点是否已经加入新点集只需要直接使用一个 vector<char> 就可以

修改原本的代码为如下：

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <set>
#include <tuple>
#include <queue>

typedef std::tuple<int, int, long long> Edge;
struct EdgeCmp {
   bool operator()(const Edge &a, const Edge &b) {
       return std::get<2>(a) > std::get<2>(b);
   } 
};
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut>> Graph;

long long prim(const Graph &g_src, int node_nr)
{
    std::vector<char> pset(node_nr + 1, 0);
    Graph g_res(node_nr + 1);
    long long res = 0;
    std::priority_queue<Edge, std::vector<Edge>, EdgeCmp> edge_heap;
    int node_added = 1;

    int start = 1; // or any, whatever
    pset[start] = 1;

    for (int i = 0; i < g_src[start].size(); i++) {
         edge_heap.push({start, g_src[start][i].first, g_src[start][i].second });
    }
    
    while (node_added < node_nr && !edge_heap.empty()) {
        int u, v;
        long long w;

        Edge edge = edge_heap.top();
        edge_heap.pop();
        if (pset[std::get<0>(edge)] == 0 || pset[std::get<1>(edge)] != 0) {
            continue;
        }

        u = std::get<0>(edge);
        v = std::get<1>(edge);
        w = std::get<2>(edge);

        pset[v] = 1;
        for (int i = 0; i < g_src[v].size(); i++) {
             edge_heap.push({v, g_src[v][i].first, g_src[v][i].second });
        }

        g_res[u].push_back({v, w});
        g_res[v].push_back({u, w});
        res += w;
        node_added++;
    }

    return node_added == node_nr ? res : -1;
}

int main(int argc, char **argv, char **envp)
{
    int n, m;

    std::cin >> n >> m;
    Graph g(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    long long res = prim(g, n);
    if (res != -1) {
        std::cout << res << std::endl;
    } else {
        std::cout << "orz" << std::endl;
    }

    return 0;
}

成功 AC，不过似乎比我们前面的 Kruskal 慢一些：

0x04. 进阶

🕊🕊🕊

ALGORITHM

#C&C++ #Algorithm #Graph Theory #Kruskal Algorithm #Spanning Tree #Minimum Spanning Tree

【ALGORITHM.0x03】求最小生成树：Kruskal与Prim算法浅析

http://example.com/2020/04/23/ALGORITHM-0X03-KRUSKAL_PRIM/

作者

arttnba3

发布于

2020年4月23日

许可协议

【ALGORITHM.0x02】Dijkstra 算法浅析上一篇

【ALGORITHM.0x01】动态规划算法浅析下一篇