C++ 深度优先搜索算法实现：求解无向图最大深度

本文将介绍如何使用 C++ 实现深度优先搜索 (DFS) 算法，并以求解无向图最大深度为例进行说明。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int g[N][N], dist, max_d = -10 * N, n, m;
bool 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]：存储图的邻接矩阵，g[i][j] 表示节点 i 到节点 j 的权值。
- dist：当前搜索路径的总权值。
- max_d：记录所有路径中最大的总权值，即最大深度。
- n：节点数量。
- m：边的数量。
- vis[N]：标记数组，vis[i] 为 1 表示节点 i 已被访问，为 0 表示未被访问。
dfs 函数:
- 参数：st 表示当前搜索的起点节点。
- 功能： 从 st 节点开始深度优先遍历图，并计算所有路径的总权值，记录最大的权值。
- 实现：
  - 遍历 st 的所有邻居节点 i。
  - 如果 i 未被访问且存在边连接 st 和 i，则将 i 标记为已访问，并更新 dist 值。
  - 递归调用 dfs(i)，从 i 节点继续深度优先搜索。
  - 回溯时，将 i 标记为未访问，并恢复 dist 值。
  - 更新 max_d 为 dist 和当前 max_d 的最大值。
- return 语句： 在本代码中，dfs 函数没有返回值，因此 return 语句可以省略。
main 函数：
- 输入图的节点数量 n 和边数量 m。
- 输入每条边的起点 x、终点 y 和权值 z。
- 遍历所有节点，以每个节点为起点调用 dfs 函数进行深度优先搜索。
- 在每次调用 dfs 函数之前，将标记数组 vis 清空。
- 最后输出 max_d，即图的最大深度。

总结

本文介绍了使用 C++ 实现深度优先搜索 (DFS) 算法，并以求解无向图最大深度为例进行说明。代码包含详细注释，解释了 DFS 函数的功能和回溯机制。DFS 算法在图论、搜索和人工智能等领域应用广泛，希望本文能帮助你更好地理解和掌握这一重要算法。