0

I'm trying to implement a program which performs a DFS Traversal. The program works fine when N is predefined to a specific value and the edges are also given actual values (please refer to the commented section of the code). The problem arises when I try to get the value of N from the user, and when I try to accept the edges from the user. I've debugged and it crashes at line adj[u].push_back(v);. However, if I write adj[0].push_back(1) i.e. actual numbers instead of variables it works fine, but it crashes when I accept u & v from the user.

#include <iostream>
#include <stack>
#include <list>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int N, M;
vector<std::list<int> > adj (N);
vector<bool> visited (N);

void dfs( int start);
int main()
{

    cin>>N>>M;
    for(int i = 0; i < M; i++ )
        {
            int u,v;
            cin>>u;
            cin>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

    /* adj[0].push_back(1);
    //   adj[1].push_back(2);
    //   adj[1].push_back(0);
    // adj[1].push_back(1);
    //  adj[2].push_back(0);
    //adj[2].push_back(1);
    // */


    std::vector<std::list<int> >::iterator i;
    int c=0;
    for(std::vector<std::list<int> >::iterator i= adj.begin(); i!=adj.end(); i++)
        {
            cout<<"Vertices connected to node "<<c<<"are ";
            std::list<int>  li=*i;
         for(std::list<int>::iterator iter = li.begin(); iter!=li.end(); iter++)
            {
                cout<<*iter<<" ";
            }
            cout<<endl;
            c++;
        }


    cout<<endl;
    cout<<"DFS TRAVERSAL"<<endl;

    dfs(0);
    cout<<endl;
    return 0;

}

void dfs( int start)
{
    stack<int> s;

    s.push(start);
    while(!s.empty())
        {
            int top=s.top();
            s.pop();
            if(visited[top]==false)
            {
                cout<<" "<<top;
                visited[top]=true;
                std::list<int> li=adj[top];
                for(std::list<int>::iterator iter= li.begin(); iter!=li.end(); iter++)
                    s.push(*iter);
            }

        }
}
user3125772
  • 73
  • 1
  • 10
  • When you do this `adj[u].push_back(v)` what is to say that `u` is in range and is a valid vector for you to try to `push_back`? – Cory Kramer Jul 01 '14 at 17:35
  • 5
    You create a vector of length N before you know what N is? – Ben Jul 01 '14 at 17:36
  • You push onto s an iterator to the local li. Once the if block exits, that iterator is no longer valid – Mike Vine Jul 01 '14 at 17:36
  • You will probably want to refresh your C++ programming skills. Take a look at [The Definitive C++ Book Guide and List](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) – Ivan Aksamentov - Drop Jul 01 '14 at 17:44
  • @Ben I'd like to create a vector that is globally accessible from anywhere. How can I do that? – user3125772 Jul 01 '14 at 17:44
  • @MikeVine How can I fix that? – user3125772 Jul 01 '14 at 17:45
  • 2
    @user3125772 - declare it (so leave off the `(N)` part), and call .resize() once you know what N is. – Ben Jul 01 '14 at 17:45
  • @user3125772: You're doing it (which is a questionable practice). But your vector is of size 0. It won't magically change size because you changed the variable you used to initially set the size. – Fred Larson Jul 01 '14 at 17:46
  • @user3125772 - The problem is not the declaration of the vector. The problem is that you haven't decided where to size the vector properly. Where you do that is up to you, but it must occur before you start accessing elements in the vector. – PaulMcKenzie Jul 01 '14 at 17:47
  • Thanks, how can I initialize all elements of 'vector visited' to false in such a way that it uses the least amount of time? (should I use a initialization loop which executes during runtime?) – user3125772 Jul 01 '14 at 17:59
  • 1
    .resize has a second argument for the value of the additional entries: `visited.resize(N, false)` should do it – Ben Jul 01 '14 at 18:07
  • Last question: How can I detect cycles here? I have CLRS and they've used a color[] array to mark back-edges. Should I create a color[] vector for the same? – user3125772 Jul 01 '14 at 18:30

0 Answers0