Depth first Traversal

Hi Experts,

I am having trouble getting the right output with using depth tree traversal.  I have my main function that creates a graph of a class (ex: wgraph g(5) <- graph of 5 nodes)  then calls a sub -function passing the graph as an argument.  In the sub function I call the (depth first) method passing in 0.  

so now I am in the depth first function and I use 0 as a starting point.  I am recursively calling this method and because I am I am using static members.  The first time through the method it works, it prints out the correct output (ex: a->b->d->g).  But the second time through (using a different number like 4)  it only prints ( ex: d)  that's it.  I tried deleting the dynamically allocated bool array but it doesn't seem to be deleting.

If you can help me figure out why it's not printing a second time I would appreciate it.

Here is the depth first method:
*********************************************************

void wgraph::depthfirst(int s) const
{            
      static bool * marked;
      static int u = -1;
            
      if(u == -1)
      {
            marked = new bool [size];
            
            for(int i = 0; i < size; i++)
            {       marked[i] = false; }
                                                
            u = s;
      }
                  
      
      marked[s] = true;
      cout << label[s];
      
      for(u = 0; u < size; u++)
      {
            if(adj_matrix[s][u] && marked[u] != true)
            {
                  cout << "->";
                  depthfirst(u);
            }       
                              
      }

      cout << endl << endl;
      if(u == s)
      {
            delete[] marked;
            u = -1;
                        
      }
      
      
}
LVL 1
nothing8171Asked:
Who is Participating?
 
ambienceConnect With a Mentor Commented:
In your solution change it to

     for(i = 0; i < size; i++)
     {
          if(adj_matrix[s][i] && marked[i] != true)
          {
               cout << "->";
               depthfirst(i);
          }      
     }
 
0
 
ambienceCommented:
I would've gone for an iterative solution to this problem. Something like

void wgraph::depthfirst(int s) const
{          
     bool* marked = new bool [size];
     for(int i = 0; i < size; i++)
     {      
           marked[i] = false;
     }
     
     while(s != -1)
     {
           marked[s] = true;
           cout << label[s];
           
           s = -1;
      for(u = 0; u < size; u++)
      {
          if(adj_matrix[s][u] && !marked[u])
          {
               s = u;
               break;
          }      
      }
     }

     cout << endl << endl;
     delete[] marked;
}
0
 
nothing8171Author Commented:
I see you made s = -1 that can't work because that is the source for the node in the graph and all it printed out was A and crashed.  

If I didn't explain it well let me know.
0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
ambienceCommented:
sorry, my mistake, that should be

void wgraph::depthfirst(int s) const
{          
     bool* marked = new bool [size];
     for(int i = 0; i < size; i++)
     {      
          marked[i] = false;
     }
     
     i = s;
     while(i != -1)
     {
          marked[s] = true;
          cout << label[s];
         
          i = -1;
          for(u = 0; u < size; u++)
          {
               if(adj_matrix[s][u] && !marked[u])
               {
                  i = s = u;
                  break;
               }      
         }
     }

0
 
ambienceCommented:
hmm .. thats not depth-first-traversal, yikes! Looks like i need to take a refresher course. Please see if the following makes sense. If it doesnt please pardon me.


void wgraph::depthfirst(int s) const
{          
     std::stack<int> stk;      
     bool* marked = new bool [size];
     for(int i = 0; i < size; i++)
     {      
          marked[i] = false;
     }
     
     stk.push(s);
     while(!stk.empty())
     {
          s = stk.top();
          stk.pop();
         
          marked[s] = true;
          cout << label[s];
         
          for(u = 0; u < size; u++)
          {
               if(adj_matrix[s][u] && !marked[u])
               {
                     stk.push(u);
               }      
         }
     }
     
     delete [] marked;
}
0
 
nothing8171Author Commented:
Ambience, your second comment was close but it's stuck in a loop somewhere.  My method I provided works except for the second time around and I think that is due to the last if statement at the bottom.
0
 
nothing8171Author Commented:
Yep I think that was it.

Thanks Ambience
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.