当前没有测试数据。

基于邻接表的DFS递归遍历详解

一、树的存储：邻接表（vector e[N]）

对于树这种无环连通图，最常用的存储方式是邻接表。我们用 vector<int> e[N] 来表示，其中：

• N 是节点的最大数量（通常设为题目节点数上限 + 10）；
• e[u] 是一个 vector，存储所有与节点 u 直接相连的节点（即 u 的邻接节点）。

由于树是无向的，所以加边时需要双向添加（比如 u 和 v 相连，要把 v 加入 e[u]，同时把 u 加入 e[v]）。

二、DFS递归遍历的核心逻辑

DFS 递归遍历树的核心是：从当前节点出发，先访问当前节点，然后递归访问所有未访问过的邻接节点。

为了防止走回头路（比如从 u 走到 v 后，又从 v 走回 u），我们需要在递归时记录父节点（即上一个访问的节点），遇到父节点时跳过即可。

三、完整代码实现（含详细注释）

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

// 定义最大节点数（根据题目需求调整，这里设为1e5+10足够大多数场景）
const int N = 100010;

// 邻接表：e[u] 存储节点 u 的所有邻接节点
vector<int> e[N];

// 存储 DFS 遍历的结果
vector<int> dfs_result;

// 加边函数：建立无向边 u-v
void add_edge(int u, int v) {
    e[u].push_back(v);  // 把 v 加入 u 的邻接表
    e[v].push_back(u);  // 把 u 加入 v 的邻接表（因为树是无向的）
}

// DFS 递归函数
// 参数说明：
//   u: 当前正在访问的节点
//   fa: 当前节点 u 的父节点（防止走回头路）
void dfs(int u, int fa) {
    // 1. 访问当前节点：将节点加入结果列表
    dfs_result.push_back(u);

    // 2. 遍历当前节点的所有邻接节点
    for (int v : e[u]) {
        // 如果邻接节点 v 是父节点 fa，说明是回头路，跳过
        if (v == fa) {
            continue;
        }
        // 3. 递归访问邻接节点 v，此时 v 的父节点是 u
        dfs(v, u);
    }
}

int main() {
    // --------------------------
    // 测试用例：构建一棵5节点的树
    // 树的结构：
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    // --------------------------
    int n = 5;  // 节点总数
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(2, 4);
    add_edge(2, 5);

    // --------------------------
    // 执行 DFS 遍历（从根节点1开始，根节点的父节点设为-1表示无父节点）
    // --------------------------
    dfs_result.clear();  // 清空结果列表
    dfs(1, -1);          // 从节点1开始DFS

    // --------------------------
    // 输出遍历结果
    // --------------------------
    cout << "DFS 遍历顺序（从节点1开始）：";
    for (int i = 0; i < dfs_result.size(); i++) {
        if (i > 0) cout << " ";
        cout << dfs_result[i];
    }
    cout << endl;

    return 0;
}

四、代码说明

1. 邻接表初始化：vector<int> e[N] 会自动初始化为空的 vector，无需额外操作。
2. 加边函数：add_edge(u, v) 双向添加边，符合树的无向特性。
3. DFS 递归函数：
   • 参数 fa 是关键，用于避免重复访问父节点；
   • 遍历顺序是“先访问当前节点，再递归访问子节点”，属于前序遍历的逻辑（对于树来说，DFS 通常默认指这种前序方式）。
4. 测试用例：构建了一棵简单的树，从根节点1开始遍历，输出结果为 1 2 4 5 3。

五、运行结果

DFS 遍历顺序（从节点1开始）：1 2 4 5 3