asked on

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;

      }


}

ambience

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;
}

nothing8171

ASKER

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.

ambience

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;
}
}
}

ambience

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;
}

nothing8171

ASKER

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.

ASKER CERTIFIED SOLUTION

ambience

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

nothing8171

ASKER

Yep I think that was it.

Thanks Ambience