Блог

Главная - Вопросы по программированию - Получение ошибки stackoverflow при выполнении DFS на графике

Получение ошибки stackoverflow при выполнении DFS на графике

#c #depth-first-search

#c #поиск в глубину

Вопрос:

Я реализую поиск в глубину на графике, чтобы найти минимальную сумму всех подключенных компонентов. Но я получаю ошибку переполнения стека. Я попытался отладить его, но не смог этого сделать.

Кто-нибудь может помочь?

Вот код:

 #include <bits/stdc  .h>

using namespace std;

void DFS(int x, vector<vector<int>> graph, vector<int> cost, vector<bool> visited, int amp;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();
}

Комментарии:

1. Попробуйте передать все векторы по ссылке вместо копирования.

2. Какова ваша среда? С каким размером графика вы имеете дело?

3. @MikeCAT Я должен сделать это для графика с миллионом узлов. Я пытаюсь запустить его на небольших входных данных, но он все еще не запущен. Кстати, я запускаю программу через терминал в Ubuntu.

4. Каков ваш вклад?

5. Для миллиона узлов у вас потенциально есть глубина стека в один миллион. Современные среды предоставляют вам всего несколько килобайт стекового пространства.

Ответ №1:

Конечно

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

должно быть

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

Вы действительно должны были заметить это в отладчике.