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;
}

DFS 的执行过程

从起点开始，访问当前节点，将其标记为已访问。
遍历当前节点的所有相邻节点，如果相邻节点未被访问，则递归访问相邻节点。
如果所有相邻节点都已被访问过，则回溯到上一个节点，继续遍历其他未访问过的相邻节点。
在回溯过程中，需要将当前节点的访问状态取消，以便后续遍历时能够访问到该节点。
统计图的深度，即从起点到最深节点的路径长度。
重复以上步骤，直到所有节点都被访问过为止。

注意事项

在遍历相邻节点时，需要判断相邻节点是否已被访问过，避免重复访问。
在回溯过程中，需要将当前节点的访问状态取消，以便后续遍历时能够访问到该节点。