Given Code: 1. Write a C++/Java function(s) that modifies the book\'s recursive

Question

Given Code:

1. Write a C++/Java function(s) that modifies the book's recursive DFS function to do the following: (a) Given an array of vertices, your algorithm tries to visit each vertex in the order provided. For example, if the order is 4 5 3 0 21, the outer layer of DFS visits vertex 4 first. If it has to come back because dfs(v) didn't mark all vertices, it will visit 5 next (unless 5 is already marked) and so on. The default ordering is naturally 01 2 3 4 5. (b) It stores the vertex marks inside of an array (basically keeps track of counts). (c) It stores the order in which vertices become dead ends are removed from the stack in an array. (d) It represents the trees in the DFS forest as a list of sets. The last two features are important for another HWK problem

Explanation / Answer

/*
* C++ Program to Traverse a Graph using DFS
*/
#include <iostream>
#include <conio.h>
using namespace std;
int c = 0;
struct node
{
char data;
int st_time, lv_time;
}*p = NULL, *r = NULL;
struct stack
{
node *pt;
stack *next;
}*top = NULL, *q = NULL, *np= NULL;
void push(node *ptr)
{
np = new stack;
np->pt = ptr;
np->next = NULL;
if (top == NULL)
{
top = np;
}
else
{
np->next = top;
top = np;
}
}
node *pop()
{
if (top == NULL)
{
cout<<"underflow ";
}
else
{
q = top;
top = top->next;
return(q->pt);
delete(q);
}
}
void create(int a[], int b[][7], int i, int j)
{
c++;
p = new node;
cout<<"enter data for new node ";
cin>>p->data;
p->st_time = c;
cout<<"start time for "<<p->data<<" is "<<c<<endl;
a[i] = 1;
push(p);
while (j < 7)
{
if ((b[i][j] == 0) || (b[i][j] == 1 && a[j] == 1))
{
j++;
}
else if (b[i][j] == 1 && a[j] == 0)
{   
create(a,b,j,0);
}
}
r = pop();
cout<<"node popped ";
c++;
cout<<"leave time for "<<r->data<<" is "<<c<<endl;
return;
}
int main()
{
int a[7];
for (int i = 0; i < 7; i++)
{
a[i] = 0;
}
int b[7][7];
cout<<"enter values for adjacency matrix"<<endl;
for (int i = 0 ; i < 7 ; i++ )
{
cout<<"enter values for "<<(i+1)<<" row"<<endl;
for (int j = 0; j < 7; j++)
{
cin>>b[i][j];
}
}
create(a,b,0,0);
getch();
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.