Solved

Depth first Traversal

Posted on 2006-11-29
7
527 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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

759 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

24 Experts available now in Live!

Get 1:1 Help Now