For the following problems, assume that vertices are ordered alphabetically in t

Question

For the following problems, assume that vertices are ordered alphabetically in the adjacency lists (thus you will visit adjacent vertices in alphabetical order). Execute a Breadth-First Search on the graph G_1, starting on vertex a. Specify the visit times for each node of the graph. Execute a Depth-First Search on the graph G_1, starting on vertex a. Specify the visit and finish times for each node of the graph (a) For each edge in your graph identify whether it is a tree edge, back edge, forward edge, or a cross edge. (b) Which edges would you remove to make your graph into a DAG?

Explanation / Answer

//explanation of question 1
#include<stdio.h>

int rear=-1,front=-1;//declare queue head and tail index intially
int queue[6];//the queue

void insert_queue(int vertex)//insert an element function for queue
{
if(rear!=5)
{

if(front==-1)
front=0;
rear=rear+1;
queue[rear]=vertex;
}
}

//delete function for the queue
int delete_queue()
{
if(front==-1||front>rear)
{printf("queue underflow ");
exit(1);
}

front=front+1;

return queue[front-1];
}

//check if queue is empty
int is_empty_queue()
{
if(front==-1||front>rear)
return 1;
else return 0;
}

int breadth_first_search(int v)//v is the starting vertex
{
int visit[6]={0};//array to keep track of visit time
int state[6];//state of each vertex changes from intial
// to waiting as it enters the queue, to visited as it leaves the queue
//to avoid multiple enteries of same vertex in array
int count=0;

int i,j,initial=1,waiting=2,visited=3;
for(i=0;i<6;i++)//intially all state of vertices set to initial
state[i]=initial;
int adj[6][6]={0};//adjacency matrix intialised to zero

adj[0][2]=1;//for an edge from i to j we put adj[i][j]=1
adj[0][5]=1;
adj[1][0]=1;
adj[2][4]=1;
adj[3][1]=1;
adj[4][3]=1;
adj[4][5]=1;
adj[5][1]=1;
printf("The vertex are visited in given order where 0 denotes vertex a,1 denotes vertex b ... so on ");
printf(" ");//for clarity empty lines are added
printf(" ");
insert_queue(v);//as we reach first vertex push it in queue
state[v]=waiting;//update its state to waiting as it is in queue
while(!is_empty_queue())//loop till queue is not empty
{ v=delete_queue();//now delete the outer vertex

state[v]=visited;//update its state to visited
visit[v]=count;//v vertex visit is update for visiting time
printf("%d(visit time: %d) ",v,visit[v] );//vertex(visit time)
count++;
//checking adajecent vertices and inserting them if state is initial
for(i=0;i<6;i++)
{
if(adj[v][i]==1 && state[i]==initial)//adajecent vertices and if state is initial
{insert_queue(i);//inserting such vertices

state[i]=waiting;//updating their state to waiting as they are now in queue
}

}
}

printf(" ");
}

//main function

int main()
{
breadth_first_search(0);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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