Solved

Depth first Traversal

Posted on 2006-11-29
7
529 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
Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

 
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

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

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

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
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 viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

786 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