is my DFS coorect?

This is a discussion on is my DFS coorect? within the C++ Programming forums, part of the General Programming Boards category; hi... i tried implementing depth first search... a part of my code is this Code: for(i=0;i<numnodes;i++) dfs(vertex[i]); } .......... void ...

  1. #1
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    is my DFS coorect?

    hi... i tried implementing depth first search...
    a part of my code is this
    Code:
    for(i=0;i<numnodes;i++)
    dfs(vertex[i]);
    }
    
    
    ..........
    
    void dfsvisit(long long int u)
    {
    cout<<"\nRECURSIVE CALL FOR"<<u;
    
    color[u]=5;
    d[u]=time1=time1+1;
    
    
    
    
    
    
    for each adjacent list 
    {
        
        adjacent_node = it1->first;
         cost = it1->second; 
          cout<<"\nADjacentfor"<<u<<" is"<<adjacent_node;
         if(color[adjacent_node]==0)
         {
           dfsvisit(adjacent_node);
          }
         }
          }
          cout<<"\ncolor of"<<u<<"is changeed to black";
         color[u]=1;
         d[u]=time1=time1+1;
        
    }
    here color 1 is black........
    0 is white .........and
    5 is grey....

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    does it compile? does it work? if not, what's the output? what's the expected output?

  3. #3
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    ya it compiles it provides partial o/p....
    for example... the number of nodes is 6
    number of edges is 8
    and the edges are
    1 2
    1 3
    2 4
    4 3
    3 2
    5 4
    5 6
    6 6
    i want to know how the actual algo prints(print statement given by me)
    and how my flow will go...
    i am trying to check the correctness...

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    There's no way we can check whether what you've typed matches what you've got written down on some piece of paper. If you want to verify that your program matches, then step through your algorithm and compare with what your program prints.

  5. #5
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    for the above test case it prints the following and gives runtime error
    DFS CALLED FOR1
    RECURSIVE CALL FOR1
    ADjacentfor1 is2
    RECURSIVE CALL FOR2
    ADjacentfor2 is4
    RECURSIVE CALL FOR4
    ADjacentfor4 is3
    RECURSIVE CALL FOR3
    ADjacentfor3 is2
    color of3is changeed to black
    ADjacentfor4 is1
    ADjacentfor4 is3
    color of4is changeed to black
    ADjacentfor2 is1
    ADjacentfor2 is4
    ADjacentfor2 is6
    RECURSIVE CALL FOR6
    ADjacentfor6 is6
    color of6is changeed to black
    ADjacentfor2 is1
    ADjacentfor2 is1
    ADjacentfor2 is17171588491051384

  6. #6
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    Unhappy

    is there abyone to help me out with understanding the bfs i implemented...
    i am with it for days.......

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem using DFS with a DAG graph
    By incognito54 in forum C Programming
    Replies: 2
    Last Post: 05-11-2005, 06:16 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21