C++ 算法技巧 — 图 (Graph)

章节概述

图由顶点和边组成，是描述事物之间关系的重要数据结构。
核心问题包括最短路径（Dijkstra）、最小生成树（Kruskal）和图的遍历。

核心原理

1. Dijkstra 算法 — 单源最短路径

贪心策略：每次选取距离源点最近的未确定顶点，用其松弛邻接顶点。

复杂度: 堆优化 O(m log n)，朴素 O(n

2. Kruskal 算法 — 最小生成树

按边权从小到大排序，逐条加入生成树。用并查集判断是否形成环。

复杂度: O(m log m)

MST 关键性质: 连接所有点的最小总代价 = n-1 条边权和。

3. 图的存储方式

方式	空间	遍历邻接	适合
邻接矩阵	O(n^2)	O(n)	稠密图
邻接表	O(n+m)	O(deg)	稀疏图

// 邻接表: vector<pair<int,int>> g[N]; // (邻居, 边权)

关键数据结构

• H_图_Graph — 图的邻接表/邻接矩阵存储
• C_堆_Heap — priority_queue 优化 Dijkstra
• K_并查集_UnionFind — Kruskal 判环

---

P3371 [模板] 单源最短路径（弱化版）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
int n, m, s, dist[10005];
vector<pii> g[10005];
 
int main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) dist[i] = INF;
    for (int i = 0, u, v, w; i < m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << (dist[i] == INF ? 0x7fffffff : dist[i]) << " ";
    return 0;
}

---

P4779 [模板] 单源最短路径（标准版）

题目: n,m ≤ 10^5，必须使用堆优化的 Dijkstra。复杂度 O(m log n)。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
typedef pair<int,int> pii;
const int INF = 1e9;
int n, m, s, dist[100005];
vector<pii> g[100005];
bool vis[100005];
 
int main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) dist[i] = INF;
    for (int i = 0, u, v, w; i < m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " ";
    return 0;
}

---

P3366 [模板] 最小生成树

#include <iostream>
#include <algorithm>
using namespace std;
 
struct Edge { int u, v, w; } e[200005];
int fa[5005];
 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool cmp(Edge a, Edge b) { return a.w < b.w; }
 
int main() {
    int n, m, ans = 0, cnt = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 0; i < m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e, e + m, cmp);
    for (int i = 0; i < m; i++) {
        int fu = find(e[i].u), fv = find(e[i].v);
        if (fu != fv) {
            fa[fu] = fv;
            ans += e[i].w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    if (cnt == n - 1) cout << ans << endl;
    else cout << "orz" << endl;
    return 0;
}

推荐练习题（洛谷）

• P3371 单源最短路径
• P4779 单源最短路径(标准版)
• P3366 最小生成树

---

相关技巧

---

• 搜索: BFS/DFS 在图上的应用
• 连通性: 并查集、最短路、生成树
• 贪心: Kruskal/Prim 最小生成树
• 优化: 堆优化 Dijkstra，读入优化
• H_图_Graph: 图的邻接表/邻接矩阵存储
• C_堆_Heap: priority_queue 优化 Dijkstra
• K_并查集_UnionFind: Kruskal 判环

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |