Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Depth first Traversal

Posted on 2006-11-29
7
Medium Priority
?
537 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
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 1500 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

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

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…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

609 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