第65章图论算法及综合应用

图论算法是处理复杂关系问题的核心工具，其中最小生成树（MST）和单源最短路是两类经典问题。最小生成树用于在连通图中寻找总权值最小的连通子图，单源最短路则用于计算从一个起点到其他所有顶点的最短路径。八级要求考生"掌握最小生成树的概念、kruskal/prim 算法，最短路径的概念、dijkstra/Floyd 算法，并灵活解决实际问题"。

图的 MST 与最短路径示意

65.1 最小生成树(Minimum Spanning Tree, MST)

65.1.1 基本概念

生成树定义：对于连通无向图，生成树是包含全部 $n$ 个顶点u、v恰好 $n-1$ 条边且无环的连通子图。最小生成树定义：带权连通无向图中，所有生成树里边权总和最小的那一棵。核心性质：

最小生成树不一定唯一，但总权值固定；
边数恒为 $n-1$ ，保证全图连通。

65.1.2 Kruskal算法

算法原理：贪心策略，先把所有边按权升序排序，依次选边，使用并查集规避环，选满 $n-1$ 条边停止。执行步骤：

全部边从小到大排序；
初始化并查集，每个顶点自成集合；
遍历每条边 $(u,v)$ ：若 $uu、vv$ 不在同一集合，加入生成树，合并集合；
累计选中边至 $n-1$ 条，结束。

#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>
using namespace std;

// 并查集结构
struct UnionFind{
    vector<int> parent;
    vector<int> rank;
    UnionFind(int n){
        parent.resize(n);
        rank.resize(n, 0);
        for(int i = 0; i < n; ++i){
            parent[i] = i;
        }
    }
    // 路径压缩查找根
    int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    // 按秩合并
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x] < rank[y]){
            parent[x] = y;
        }else{
            parent[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
};

// Kruskal求最小生成树，返回总权值，不连通返回-1
int kruskal(int n, vector<tuple<int, int, int>>& edges) {
    sort(edges.begin(), edges.end(), [](const tuple<int,int,int>&a, const tuple<int,int,int>&b){
        return get<2>(a) < get<2>(b);
    });
    UnionFind uf(n);
    int totalWeight = 0;
    int edgeCount = 0;
    for(auto& e : edges){
        int u = get<0>(e);
        int v = get<1>(e);
        int w = get<2>(e);
        if(uf.find(u) != uf.find(v)){
            uf.unite(u, v);
            totalWeight += w;
            edgeCount++;
            if(edgeCount == n-1) break;
        }
    }
    return edgeCount == n-1 ? totalWeight : -1;
}

算法复杂度： $O(e \log e)$ ，适合稀疏图。

65.1.3 Prim算法

算法原理：从任意顶点开始维护生成树集合，每次选取连接树内外权值最小的边扩展。执行步骤：

初始化lowCost数组，记录各点到当前树的最小边权；起点权值置0；
循环选出不在树中u、vlowCost最小的顶点加入树；
用该点更新所有邻点的lowCost；
全部顶点入树则结束。

#include <vector>
#include <climits>
using namespace std;

// 邻接矩阵版Prim，返回总权，不连通返回-1
int prim(int n, const vector<vector<int>>& graph){
    const int INF = INT_MAX;
    vector<int> lowCost(n, INF);
    vector<bool> inMST(n, false);
    lowCost[0] = 0;
    int totalWeight = 0;
    int count = 0;
    for(int i = 0; i < n; ++i){
        int u = -1;
        int minW = INF;
        // 找未入树最小权顶点
        for(int v = 0; v < n; ++v){
            if(!inMST[v] && lowCost[v] < minW){
                minW = lowCost;
                u = v;
            }
        }
        if(u == -1) return -1;
        inMST[u] = true;
        totalWeight += minW;
        count++;
        // 更新邻接点代价
        for(int v = 0; v < n; ++v){
            if(!inMST[v] && graph[u][v] != 0 && graph[u][v] < lowCost[v]){
                lowCost[v] = graph[u][v];
            }
        }
    }
    return count == n ? totalWeight : -1;
}

复杂度：邻接矩阵 $O(n^2)$ ，适合稠密图。

65.1.4 Kruskal与Prim对比

算法	核心思路	稀疏图复杂度	稠密图复杂度	适用场景
Kruskal	排序选边，并用并查集避环	$O(e\log e)$	$O(e\log e)$	边少的稀疏图
Prim	逐步扩展生成树	$O(e\log n)$	$O(n^2)$	顶点少稠密图

65.2 单源最短路(Single-Source Shortest Paths)

65.2.1 基础定义

单源最短路：给定起点 $s$ ，求 $s$ 到其余所有顶点的最短路径总权。负权边：边权小于0；负权环：环总权为负，存在则无最短路径。

Dijkstra 遇到负权会"翻车"

Dijkstra 基于"每次确定的最短路不会再被更新"的贪心假设，一旦存在负权边该假设就不成立，结果可能错误。图中若存在负权，必须改用 Bellman-Ford 或 SPFA；仅有负权环时才无解（Floyd 也只能检测、不能求最短路）。

65.2.2 Dijkstra算法

适用：无负权图，贪心策略，优先队列优化。

#include <vector>
#include <queue>
#include <climits>
using namespace std;

vector<int> dijkstra(int n, const vector<vector<pair<int, int>>>& adj, int s){
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        auto cur = pq.top();
        pq.pop();
        int u = cur.second;
        if(visited[u]) continue;
        visited[u] = true;
        for(auto& edge : adj[u]){
            int v = edge.first;
            int w = edge.second;
            if(dist[u] != INF && dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

复杂度： $O((n+e)\log n)$ ，不能处理负权。

65.2.3 Floyd算法

动态规划，求任意两点间最短路，允许负权（无负环）。

#include <vector>
#include <iostream>
#include <climits>
using namespace std;
const int INF = INT_MAX / 2;

void floyd(int n, vector<vector<int>>& dist) {
    for(int k = 0; k < n; ++k){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(dist[i][k] + dist[k][j] < dist[i][j]){
                    dist[i][j] = dist[i][k] + dist[k];
                }
            }
        }
    }
}

复杂度 $O(n^3)$ ，顶点数量少时使用。

65.2.4 Bellman-Ford算法

支持负权，可检测负权环，对全部边循环松弛 $n-1$ 次。

#include <vector>
#include <tuple>
#include <climits>
using namespace std;

pair<vector<int>, bool> bellmanFord(int n, const vector<tuple<int,int,int>>& edges, int s){
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    dist[s] = 0;
    bool hasNegativeCycle = false;
    // n-1轮松弛
    for(int i = 0; i < n-1; ++i){
        bool update = false;
        for(auto& e : edges){
            int u = get<0>(e);
            int v = get<1>(e);
            int w = get<2>(e);
            if(dist[u] != INF && dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                update = true;
            }
        }
        if(!update) break;
    }
    // 检测负环
    for(auto& e : edges){
        int u = get<0>(e);
        int v = get<1>(e);
        int w = get<2>(e);
        if(dist[u] != INF && dist[v] > dist[u] + w){
            hasNegativeCycle = true;
            break;
        }
    }
    return {dist, hasNegativeCycle};
}

复杂度 $O(n \times e)$ ，效率偏低，适合小规模带负权图。

65.3 算法对比总结

MST：稀疏用Kruskal，稠密用Prim；
单源最短路无负权选Dijkstra；
全点最短路u、v允许负权无环选Floyd；
需要判断负环使用Bellman-Ford。

65.4 真题示例（最小生成树总代价）

【GESP 八级风格·编程题】 题目描述：某地区有 $n$ 个村庄（编号 0~n-1），要在村庄之间修路使所有村庄连通，且总修路代价最小。给定 $m$ 条可修路信息，每条为 u v w（村庄 u 与 v 之间修路代价为 w）。求最小总代价；若无法使所有村庄连通，输出 -1。 输入格式：第一行 $n, m$ ；之后 $m$ 行每行 $u, v, w$ 。 输出格式：一个整数（最小总代价，或 -1）。 样例输入：
4 5
0 1 2
0 2 3
1 2 1
1 3 4
2 3 5
样例输出：7（选边 1-2(1)、0-1(2)、1-3(4)）

参考解答（Kruskal + 并查集）：

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

struct UnionFind {
    vector<int> parent, rank;
    UnionFind(int n) {
        parent.resize(n);
        rank.assign(n, 0);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;          // 已连通，会形成环
        if (rank[x] < rank[y]) parent[x] = y;
        else { parent[y] = x; if (rank[x] == rank[y]) rank[x]++; }
        return true;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> edges;     // (u, v, w)
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        edges.emplace_back(u, v, w);
    }
    sort(edges.begin(), edges.end(),
         [](auto &a, auto &b) { return get<2>(a) < get<2>(b); });  // 按权升序
    UnionFind uf(n);
    long long total = 0;
    int cnt = 0;
    for (auto &e : edges) {
        int u = get<0>(e), v = get<1>(e), w = get<2>(e);
        if (uf.unite(u, v)) {               // 不连通才选入生成树
            total += w;
            if (++cnt == n - 1) break;       // 选满 n-1 条边即可
        }
    }
    cout << (cnt == n - 1 ? total : -1) << endl;
    return 0;
}

为什么样例输出是 7？

排序后边权为 1(1-2)、2(0-1)、3(0-2)、4(1-3)、5(2-3)。贪心选 1-2（连通2）、0-1（连通2）、1-3（连通全部 4 个点，已选 3=n-1 条边）停止，总权 $1+2+4=7$ 。边 0-2、2-3 因会成环被跳过。

练习题

说明

下列选择题考查 MST 与最短路的算法选择、复杂度与特性，参考答案默认折叠，点击"参考答案"展开。

1.（MST 性质） 含 $n$ 个顶点的连通无向图，其最小生成树一定有多少条边？

A. $n$
B. $n-1$
C. $n+1$
D. 不一定

参考答案

B。生成树必须连通且无环，恰好包含 $n$ 个顶点和 $n-1$ 条边。

2.（Kruskal） Kruskal 算法中用于"避免选边成环"的核心数据结构是？

A. 优先队列
B. 并查集
C. 哈希表
D. 栈

参考答案

B。Kruskal 把边按权排序后逐条尝试加入，用并查集判断两端是否已连通，连通则跳过以避免成环。

3.（Dijkstra） 关于 Dijkstra 算法，错误的是？

A. 适用于无负权边的图
B. 可用优先队列优化到 $O((n+e)\log n)$
C. 能正确处理含负权边的图
D. 求单源最短路

参考答案

C。Dijkstra 的贪心假设在负权边下不成立，不能正确处理负权；负权图需改用 Bellman-Ford / SPFA。

4.（Floyd） Floyd 算法用于求解什么问题，时间复杂度是多少？

A. 单源最短路， $O(n^2)$
B. 任意两点最短路， $O(n^3)$
C. 最小生成树， $O(e\log e)$
D. 拓扑排序， $O(n+e)$

参考答案

B。Floyd 基于动态规划求任意两点间最短路，三重循环，复杂度 $O(n^3)$ ，适合顶点数不大的图。

5.（算法选择） 一个 $n=2000, e=5000$ 的稀疏图求最小生成树，优先选？

A. Prim（邻接矩阵）
B. Kruskal
C. Dijkstra
D. Floyd

参考答案

B。稀疏图（边少）优先 Kruskal，复杂度 $O(e\log e)$ 与 $n$ 关系不大；Prim 邻接矩阵 $O(n^2)$ 在此 $n$ 较大时不占优；C、D 不是 MST 算法。