не удается найти ошибку в коде поиска в глубину, который выполняется вечно

Question

Попытка реализовать поиск в глубину.Реализован список смежности с использованием вектора.Отслеживание вершин, которые были исследованы набором "исследуется".«s» - начальная вершина.Я думаю, что проблема в цикле, но не могу понять.

void AddEdge(vector<vector<int>>& adjList, int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u);
}

    void dfs(vector<vector<int>>& adjList, int s) {
    stack<int> adjacent;
    set<int> explored;
    adjacent.push(s);
    while(adjacent.size() != 0) {
        int vertex = adjacent.top();
        adjacent.pop();
        if(explored.count(vertex) == 0)
            explored.insert(vertex);
            for(vector<int>::iterator itr = adjList[vertex].begin(); 
                    itr != adjList[vertex].end(); ++itr) {
                adjacent.push(*itr);
            }
    }
    for(set<int>::iterator itr = explored.begin(); itr != explored.end(); 
        ++itr) {
        cout << "vertices reachable from " << s << " are " << "--> " << * 
        (itr);
    }
    }

Заранее спасибо.

Answer 1

Ваш отступ вводит вас в заблуждение: цикл for не находится внутри блока if, поэтому adjacent также получит соседей посещенных вершин.Это гарантирует, что внешний цикл никогда не заканчивается.

Исправьте, добавив фигурные скобки:

    if(explored.count(vertex) == 0) { // <-- brace
        explored.insert(vertex);
        for(vector<int>::iterator itr = adjList[vertex].begin(); 
                itr != adjList[vertex].end(); ++itr) {
            adjacent.push(*itr);
        }
    } // <-- brace