图论：遍历与最短路

图基础

图由顶点（V）和边（E）构成。按方向分有向/无向图，按权重分加权/无权图。C++ 中最常用邻接表（vector'<'vector'<'pair'<'int,int'>''>''>'）存图。

// Adjacency list (weighted directed graph)
int n; // number of vertices
vector<vector<pair<int,int>>> adj(n); // adj[u] = {(v, weight), ...}
adj[u].push_back({v, w}); // add edge u -> v with weight w

图的表示

算法复杂度对比

BFS & DFS

BFS（广度优先）用队列逐层展开，天然给出无权图最短路。DFS（深度优先）用栈（或递归）深入分支，适合连通性、环检测、拓扑后序。

BFS 适用场景

• 无权图单源最短路（步数/距离）
• 二部图判断（BFS 2-着色）
• 多源 BFS（同时从多个起点扩散）
• 127. 单词接龙、200. 岛屿数量

// BFS: shortest path in unweighted graph (adjacency list)
// Returns dist[] from src; dist[v] == -1 means unreachable
vector<int> bfs(int n, vector<vector<int>>& adj, int src) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

DFS 适用场景

• 连通分量计数
• 有向图环检测（白/灰/黑三色标记）
• 拓扑排序的后序 DFS
• 207. 课程表、133. 克隆图

// DFS: count connected components (undirected graph)
void dfs(int u, vector<vector<int>>& adj, vector<bool>& vis) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v, adj, vis);
}

int countComponents(int n, vector<vector<int>>& adj) {
    vector<bool> vis(n, false);
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (!vis[i]) { dfs(i, adj, vis); cnt++; }
    return cnt;
}

visited 的位置：BFS 中入队时立即标记 visited（防止重复入队）；DFS 中进入前标记（或用 path 集合记录当前递归路径以检测环）。

拓扑排序

拓扑排序适用于有向无环图（DAG），给出一个所有「依赖在被依赖之前」的线性顺序。两种实现：

两种实现

// Kahn's topological sort (BFS, detects cycles)
// Returns empty vector if graph has a cycle
vector<int> topoSort(int n, vector<vector<int>>& adj) {
    vector<int> indegree(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) indegree[v]++;
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indegree[v] == 0) q.push(v);
    }
    return (int)order.size() == n ? order : vector<int>{}; // empty = cycle
}

典型题目

• 207. 课程表（判断是否有环）
• 210. 课程表 II（输出拓扑顺序）
• 1462. 课程表 IV（拓扑 + 可达性）

环检测：Kahn 算法结束后若仍有节点未被移除，则图中存在环。DFS 中若遇到「灰色」（当前路径上）节点则有环。

Dijkstra 最短路

Dijkstra 适用于非负权图，贪心地从距离最小的节点扩展。堆优化版时间 O((V+E) log V)。

算法步骤

1. 初始化 dist[src] = 0，其余 = INF，将 (0, src) 入最小堆
2. 每次弹出堆顶 (d, u)；若 d > dist[u] 则跳过（旧数据）
3. 遍历 u 的所有邻居 v，若 dist[u] + w < dist[v] 则松弛并入堆
4. 所有节点处理完毕，dist[] 即为各顶点最短距离

// Dijkstra with min-heap (adjacency list of (neighbor, weight))
// Returns dist[] from src
vector<long long> dijkstra(int n, vector<vector<pair<int,int>>>& adj, int src) {
    const long long INF = 1e18;
    vector<long long> dist(n, INF);
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue; // stale entry
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

典型题目

• 743. 网络延迟时间
• 1631. 最小体力消耗路径
• 787. K 站中转内最便宜的航班（改用 Bellman-Ford）

负权边：Dijkstra 不能处理负权边（贪心前提：已确定最短距离的节点不会被更新）。有负权边用 Bellman-Ford 或 SPFA。