Solved

Depth first Traversal

Posted on 2006-11-29
7
528 Views
Last Modified: 2010-04-01
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;
                        
      }
      
      
}
0
Comment
Question by:nothing8171
  • 4
  • 3
7 Comments
 
LVL 22

Expert Comment

by:ambience
ID: 18043135
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
 
LVL 1

Author Comment

by:nothing8171
ID: 18043156
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
 
LVL 22

Expert Comment

by:ambience
ID: 18043187
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 22

Expert Comment

by:ambience
ID: 18043207
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
 
LVL 1

Author Comment

by:nothing8171
ID: 18043303
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
 
LVL 22

Accepted Solution

by:
ambience earned 500 total points
ID: 18043527
In your solution change it to

     for(i = 0; i < size; i++)
     {
          if(adj_matrix[s][i] && marked[i] != true)
          {
               cout << "->";
               depthfirst(i);
          }      
     }
 
0
 
LVL 1

Author Comment

by:nothing8171
ID: 18048432
Yep I think that was it.

Thanks Ambience
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

863 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

28 Experts available now in Live!

Get 1:1 Help Now