-1

Trying to implement Depth First Search. Implemented adjacency list using vector. Keeping track of vertices that have been explored by set "explored". "s" is the starting vertex. I think the problem is in while loop but can't figure out. 

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);
    }
    }

Thanks in advance.

frustbuzzly
  • 1
  • I think this can help you: https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems – Eljay Sep 22 '19 at 18:18
  • Please see https://ericlippert.com/2014/03/05/how-to-debug-small-programs/. – eesiraed Sep 22 '19 at 18:25
  • You're pushing elements that already have been visited. I don't think this will cause an endless loop (as they should get ignored when re-visiting), but at least slow down your algorithm. Better: `while() { pop(); explored.insert(); for() { if(!explored) { push(); } } }` – Aconcagua Sep 22 '19 at 18:36

1 Answers1

0

Your indentation is misleading you: the for loop is not inside the if block, and so it will make that adjacent gets the neighbors of visited vertices too. That ensures that the outer loop never ends.

Fix by adding braces:

    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
trincot
  • 317,000
  • 35
  • 244
  • 286