图的遍历（点 / 边 / 路径）—— C++ 模板与 visited 的本质

二叉树刷题那篇（二叉树刷题总结）讲了”遍历 + 分解”两种思维。这篇补上图的部分：点、边、路径三种遍历，邻接矩阵 / 邻接表两种存法都写 C++ 模板，重点厘清 visited 到底解决什么、为什么二叉树不需要它、以及路径遍历为什么还要额外的存储变量。

图上的 Dijkstra 扩散（1/edge_weight 作跳转成本）正是 GraphRAG（Chunk 级遍历版）的检索核心，这篇是它的底层算法。

一、图的三要素：点、边、路径

要素	定义	关键点
点 vertex / node	实体、状态、位置	存”是什么”
边 edge	两点间的关系	可带方向（有向图）、权重（有权图）、类型
路径 path	顶点序列，相邻两点间有边	`v1 → v2 → v3`

二、两种存法

存法	空间	找邻居	适合
邻接矩阵 `g[v][v]`	O(V²)	O(V)，任意两点查边 O(1)	稠密图
邻接表 `adj[v]→列表`	O(V+E)	O(邻居数)	稀疏图（实际大多数情况）

#include <bits/stdc++.h>
using namespace std;

int n, m;                       // 点数、边数

// ---- 邻接矩阵：g[u][v] = 边权（无权用 1），0 = 无边 ----
vector<vector<int>> g(n, vector<int>(n, 0));
// 读边：g[u][v] = g[v][u] = w;   （有向只写一行）

// ---- 邻接表：adj[u] = {(邻居v, 边权w), ...}；无权可省 w ----
vector<vector<pair<int, int>>> adj(n);
// 读边：adj[u].push_back({v, w}); adj[v].push_back({u, w});   （有向只写一行）

DFS/BFS 在两种表示下都能跑，复杂度：邻接表 O(V+E)，矩阵 O(V²)。

三、点的遍历：DFS / BFS

点遍历解决”从某点出发能到哪些点”。图有环，必须 visited。

3.1 DFS（栈 / 递归，一条路走到底）

// 矩阵版
vector<bool> vis(n, false);
function<void(int)> dfs = [&](int u) {
    vis[u] = true;
    // 处理点 u
    for (int v = 0; v < n; ++v)
        if (g[u][v] && !vis[v])
            dfs(v);
};

// 表版
vector<bool> vis(n, false);
void dfs(int u) {
    vis[u] = true;
    for (auto [v, w] : adj[u])
        if (!vis[v]) dfs(v);
}

3.2 BFS（队列，一层一层扩）

BFS 天然给出无权图最短路径。入队时就标记，不是出队时——否则一个点会被多个邻居重复推入队，最坏 O(V²)。

// 矩阵版：dist[v] = s 到 v 步数，-1 未到。dist 兼任 visited + 最短距离
vector<int> bfs(int s) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 0; v < n; ++v)
            if (g[u][v] && dist[v] == -1) {
                dist[v] = dist[u] + 1;   // 先到者最短
                q.push(v);
            }
    }
    return dist;
}

// 表版
void bfs(int s) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : adj[u])
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
    }
}

四、visited 的本质与二叉树的例外

4.1 visited 解决两件事

防重复访问：每个点被多个邻居触发时，只算一次
防死循环：有环图上不标记，递归无限套娃 → 栈溢出

// 图，环存在。没有 vis：1→2→3→1 无限循环
void dfs(int u) {
    for (auto [v, w] : adj[u])
        if (!vis[v]) dfs(v);
}

4.2 为什么二叉树不需要 visited

二叉树天生无环，且每个节点只有一条父路径能到达（单亲）——所以：

不可能重复访问：每个点只会被它的唯一父节点触发一次
不会死循环：没有环，递归必然终止（深度 = 树高）

visited 是空转——写上不报错，纯属白写：

// 树：天然无环 + 单亲，去掉 visited 依然正确终止
void dfs(int u) {
    for (auto [v, w] : adj[u])   // 或 dfs(left); dfs(right);
        dfs(v);
}

注意：树不用 visited 不是”树上的 DFS 不是 DFS”。DFS 还是 DFS，只是树把防重这个职责让结构扛了。别误解成”树只在深层走、图不是”——图也是深度优先往深层走，区别在会不会绕回来：树到叶子自然停（深度有限），图会顺着环绕回（深度无限），没有 visited 停不下来。

结构	需 visited 吗	原因
图（有环）	必用	防重复访问 + 防死循环
树（无环单亲）	不用	结构保证不重访
DAG（无环）	看情况	有公共子节点就可能重访

五、边的遍历

5.1 枚举所有边（纯读，做汇总 / 过滤）

// 矩阵版：只扫上半三角，自动去重
for (int u = 0; u < n; ++u)
    for (int v = u + 1; v < n; ++v)
        if (g[u][v]) { /* 处理边 (u,v,w) */ }

// 表版：u<v 去重；有向免去重
for (int u = 0; u < n; ++u)
    for (auto [v, w] : adj[u])
        if (u < v) { /* 处理边 (u,v,w) */ }

纯枚举不需要任何标记。

5.2 DFS 给边分类：树边 / 返边

判环、Tarjan、桥的前置。用 tin 时间戳，不是普通 visited——tin 干两份活：当 visited 用（== -1 判断来过没有）+ 记录发现顺序（判”返边”靠”v 是不是 u 的祖先”，光靠 visited 判不了先后）。

vector<int> tin(n, -1);
int timer = 0;
// 表版；矩阵版只换邻居枚举
void dfs_edges(int u, int p) {
    tin[u] = timer++;
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;               // 往回走的树边，跳过
        if (tin[v] == -1) dfs_edges(v, u);  // 树边（首次发现）
        /* else：返边 u→v，v 是 u 的祖先（有环） */
    }
}

六、路径的遍历

6.1 枚举 s→t 的所有简单路径（回溯）

路径遍历除了防重，还要存路径。两个额外变量：

path：存当前路径
on_path：标记当前路径上的点，防重复经过

vector<int> path;
vector<bool> on_path(n, false);
// 表版；矩阵版把邻居循环换成 for v in 0..n-1
void dfs_paths(int u, int t) {
    on_path[u] = true;
    path.push_back(u);
    if (u == t) { /* 处理 path：一条完整路径 */ }
    else for (auto [v, w] : adj[u])
        if (!on_path[v])
            dfs_paths(v, t);
    path.pop_back();
    on_path[u] = false;       // 关键：回溯复位！
}

陷阱：on_path 必须在递归后复位。否则第一条路走完、换路时，别的路径想再经过 u 会被挡死 → 漏路径。

vis 和 on_path 是两种东西：

标记	性质	生命周期
`vis`（点遍历）	永久，清不回	整个图遍历一遍就结束
`on_path`（路径枚举）	临时，回溯复位	只标记”当前这条路上”，换路放行

6.2 最短路径 + 还原

无权图用 BFS + prev 前驱；加权图把 BFS 换成 Dijkstra，prev 逻辑相同。

vector<int> prev(n, -1);                 // prev[v] = 最短路径上 v 的前驱
void bfs_shortest(int s) {
    queue<int> q;
    prev[s] = s; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : adj[u])
            if (prev[v] == -1) {
                prev[v] = u;             // 先到者定前驱
                q.push(v);
            }
    }
}
vector<int> reconstruct(int s, int t) {  // 还原 s→t 的路径
    if (prev[t] == -1) return {};        // 不可达
    vector<int> p;
    for (int cur = t;; cur = prev[cur]) {
        p.push_back(cur);
        if (cur == s) break;
    }
    reverse(p.begin(), p.end());
    return p;                            // 无权图必是最短路径
}

七、遍历 vs 分解：树和图的分野

二叉树刷题那篇说”DFS = 遍历 + 分解两种思维”。分解（分治）思想在图里存在，但只在”图结构允许子问题独立”时能用。

树：子树是独立子问题，f(node) = combine(f(left), f(right))，父问题解 = 子问题解拼接 → 分解可行且高效
图：没有天然分割，一个节点连向四面八方，子问题重叠、互相共享状态 → 通用图上分解会重复计算

结构	能分解吗	为什么
树	能，还最优	子树独立，无重叠
DAG	有条件	拓扑序 + 记忆化
连通分量	能（整体层面）	块间无连接
一般有环图	难	子问题重叠，遍历兜底

一个例子：数路径条数。

// 树：分解，子问题独立，不用 visited
int count_paths(node) {
    if (!node) return 0;
    return 1 + count_paths(node->left) + count_paths(node->right);
}

// 图：不能分解，子问题重叠，visited + 回溯
int count_paths(u, t, visited) {
    if (u == t) return 1;
    int total = 0;
    for (auto [v, w] : adj[u])
        if (!visited[v]) {
            visited[v] = true;
            total += count_paths(v, t, visited);
            visited[v] = false;   // 回溯复位
        }
    return total;
}

图要分解，得先解决”怎么把图切成独立块”——这本身就是个图问题（割点、连通分量、桥）。

八、总结

每种遍历要什么标记，总账：

遍历	需要什么	额外变量
点遍历 DFS/BFS	`vis`（必用）	BFS 的 `dist` 兼任距离
边枚举	无	无
边分类	`tin` 时间戳	无（既是防重又是判环依据）
路径枚举	`on_path` + 复位	`path` 存路径
最短路径	BFS/Dijkstra	`prev` 前驱 + 还原

一句话：visited 是图特有的防御（防环 / 防重），树靠结构干净免了；path 是路径问题特有的存储，树和图都要。图的默认武器是遍历，树的默认武器是分解——不是图不能分解，是图要先付出”找独立子问题”的代价，而树天生自带。