图论：遍历与最短路

图基础

图由顶点（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。

Bellman-Ford 最短路

Bellman-Ford 适用于含负权边的图，对所有边执行 n-1 轮松弛，可同时检测负环。时间 O(VE)，比 Dijkstra 慢，但适用范围更广。

算法步骤

1. 初始化 dist[src] = 0，其余 = INF
2. 重复 n-1 次：遍历所有边 (u, v, w)，若 dist[u] ≠ INF 且 dist[u]+w < dist[v] 则松弛
3. 第 n 轮：若仍发生松弛 → 图中存在从 src 可达的负环

// Bellman-Ford: single-source shortest path (supports negative edges)
struct Edge { int u, v, w; };

// Returns dist[] from src, or empty vector if a negative cycle is reachable
vector<int> bellmanFord(int n, vector<Edge>& edges, int src) {
    const int INF = 1e9;
    vector<int> dist(n, INF);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {         // n-1 relaxation rounds
        for (auto& [u, v, w] : edges)
            if (dist[u] != INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
    }
    for (auto& [u, v, w] : edges)              // round n: check negative cycle
        if (dist[u] != INF && dist[u] + w < dist[v])
            return {};                          // negative cycle detected
    return dist;
}

vs Dijkstra

SPFA：SPFA 是 Bellman-Ford 的队列优化版，平均 O(kE)，但最坏仍 O(VE)。竞赛中某些题专门卡 SPFA，工程中优先用 Dijkstra 或确定无负环再用 SPFA。

二部图检测与 DFS 染色

二部图可将节点分为两个集合，所有边跨越两集合。等价条件：图中无奇数环。检测方法：DFS/BFS 2-染色——相邻节点染不同颜色，若出现同色相邻则非二部图。

2-染色（无向图）

颜色 0 和 1 交替染色。BFS/DFS 时对未染色邻居染相反色；若邻居已染且颜色与当前相同，则非二部图。需处理非连通图（对每个未访问节点单独启动）。

// BFS 2-coloring: bipartite check (undirected graph, handles disconnected)
bool isBipartite(int n, vector<vector<int>>& adj) {
    vector<int> color(n, -1);
    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;
        queue<int> q;
        q.push(start); color[start] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); }
                else if (color[v] == color[u]) return false;
            }
        }
    }
    return true;
}

3-色标记（有向图环检测）

白色（0）= 未访问；灰色（1）= 在当前 DFS 路径上（递归栈中）；黑色（2）= 已完全访问。遇到灰色节点说明发现回边（back edge）→ 有环。与拓扑排序的 Kahn 算法等价。

// DFS 3-color cycle detection for directed graphs
// 0=white(unvisited), 1=gray(on stack), 2=black(done)
bool hasCycle(int n, vector<vector<int>>& adj) {
    vector<int> color(n, 0);
    function<bool(int)> dfs = [&](int u) -> bool {
        color[u] = 1;                  // gray — on current path
        for (int v : adj[u]) {
            if (color[v] == 1) return true;              // back edge → cycle
            if (color[v] == 0 && dfs(v)) return true;
        }
        color[u] = 2;                  // black — fully done
        return false;
    };
    for (int i = 0; i < n; i++)
        if (color[i] == 0 && dfs(i)) return true;
    return false;
}