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; // 此处 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 函数中的 return 语句

在这个代码里，dfs 函数的返回值是 void，即没有返回值。因此，return 语句在这个代码中没有实际作用，可以省略。

总结

本文通过求解最大深度路径问题，详细讲解了 C++ 中的深度优先搜索 (DFS) 算法，并对代码中的关键部分进行了分析。希望本文能够帮助你更好地理解 DFS 算法的原理和应用。