C++ 深度优先搜索（DFS）算法实现：图的最大深度

C++ 深度优先搜索 (DFS) 算法实现：图的最大深度

本文将介绍如何使用 C++ 实现深度优先搜索 (DFS) 算法来查找无向图中从任意节点出发所能到达的最大深度。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int g[N][N], dist, max_d = -10 * N, n, m;
boolean vis[N];

void dfs(int st) {
    for (int i = 1; i <= n; i++) {
        if (g[st][i] && !vis[i]) {
            vis[i] = 1;
            dist += g[st][i];
            dfs(i);
            dist -= g[st][i]; // 回溯
        }
    }
    max_d = max(max_d, dist); // 统计最大深度
    vis[st] = 0; // 回溯
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z; // 读入边和对应的权值
        g[x][y] = z;
        g[y][x] = z;
    }
    for (int i = 1; i <= n; i++) {
        vis[i] = 1;
        dfs(i);
        memset(vis, 0, sizeof(vis)); // 记得清空标记数组
    }
    cout << max_d;
    return 0;
}

代码解释

初始化: 代码首先定义了图的邻接矩阵 g[N][N]、当前路径长度 dist、最大深度 max_d、节点数量 n、边数量 m 和标记数组 vis[N]，用于记录节点是否被访问过。
DFS 函数: dfs(int st) 函数实现深度优先搜索算法。
- 遍历相邻节点: 函数遍历与当前节点 st 相邻的所有节点 i。
- 访问判断: 如果节点 i 未被访问过 (!vis[i]) 且存在边连接 (g[st][i])，则将其标记为已访问 (vis[i] = 1)，更新当前路径长度 (dist += g[st][i])，并递归调用 dfs(i) 继续搜索。
- 回溯: 递归调用结束后，需要回溯到上一个节点，因此将当前路径长度减去边的权值 (dist -= g[st][i])，并将节点 i 的访问标记清除 (vis[i] = 0)。
- 更新最大深度: 在遍历完当前节点的所有相邻节点后，将当前路径长度 dist 与最大深度 max_d 进行比较，并更新 max_d。
主函数: main() 函数首先读取图的节点数量 n 和边数量 m，然后读取每条边的信息（起点、终点和权值），并将信息存入邻接矩阵 g[N][N] 中。
- 遍历所有节点: 主函数循环遍历每个节点 i，并以其作为起点进行 DFS 搜索。
- 清空标记数组: 在每次 DFS 搜索之前，需要将 vis 数组清空，以确保每个节点都能被遍历到。
- 输出最大深度: 最后，主函数输出计算得到的最大深度 max_d。

回溯机制

在 DFS 中，回溯指的是在遍历完当前节点的所有相邻节点后，回到上一个节点，并恢复该节点的状态。在代码中，回溯主要通过以下两个操作实现：

更新路径长度: dist -= g[st][i] 将当前路径长度减去边的权值，以回到上一个节点。
取消标记: vis[i] = 0 将节点 i 的访问标记清除，使其可以被其他节点访问。

vis 数组的作用

vis 数组的作用是记录每个节点是否已经被访问过，避免重复访问和死循环。在 DFS 的过程中，每个节点只会被访问一次，如果一个节点被访问过，则将其标记为已访问，下次遍历到该节点时，就不会再访问它。

总结

本文介绍了使用 C++ 实现 DFS 算法来查找图中最大深度的代码实现和代码解释，并详细阐述了回溯机制和 vis 数组的作用。DFS 算法是图算法中的基本算法，可以应用于很多问题，例如拓扑排序、寻找连通分量等。