在图形上执行 DFS 时出现 stackoverflow 错误

Question

我正在对图实施深度优先搜索，以找到所有连通分量的最小总和。但是我收到堆栈溢出错误。我尝试调试它，但失败了。

有人可以帮忙吗？

代码如下：

#include <bits/stdc++.h>

using namespace std;

void DFS(int x, vector<vector<int>> graph, vector<int> cost, vector<bool> visited, int &c)
{
    c = min(c, cost[x]);
    visited[x] = true;
    for (int n = 0; n < (int)graph[x].size(); n++)
    {
        if (!visited[graph[x][n]])
            DFS(x, graph, cost, visited, c);
    }
}

void solve()
{
    int nodes, edges;
    cin >> nodes >> edges;

    vector<int> cost(nodes);
    vector<bool> visited(nodes);
    vector<vector<int>> graph(nodes);

    for (int i = 0; i < nodes; i++)
        cin >> cost[i];

    for (int i = 0; i < edges; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a - 1].push_back(b - 1);
        graph[b - 1].push_back(a - 1);
    }
    int ans = 0;
    for (int i = 0; i < nodes; i++)
    {
        if (!visited[i])
        {
            int c = cost[i];
            DFS(i, graph, cost,visited, c);
            ans += c;
        }
    }
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
}

Answer 1

当然

DFS(x, graph, cost, visited, c);

应该是

DFS(graph[x][n], graph, cost, visited, c);

你真的应该在调试器中注意到这一点。

在图形上执行 DFS 时出现 stackoverflow 错误

Getting stackoverflow error while doing DFS on a graph

c++

depth-first-search