Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Question 2 : Consider the following directed graph: ( 2 . 1 ) Draw the D F S - forest obtained by running algorithm DFS

Question 2: Consider the following directed graph:
(2.1) Draw the DFS-forest obtained by running algorithm DFS. Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS-forest, give the pre- and post-number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically first.
(2.2) Draw the DFS-forest obtained by running algorithm DFS. Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS-forest, give the pre- and post-number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically last.
Note that in (2.1) algorithm DFS(G) starts by calling Explore(A), Explore for vertex A.
Note that in (2.2) algorithm DFS(G) starts by calling Explore(G), Explore for vertex G.
Algorithm DFS (G) :
for each vertex v
do visited(v)= false
endfor;
clock =1;
for each vertex v
do if visited(v)= false
then ExPLORE(v)
endif
endfor
Algorithm Explore (v) :
visited(v)= true;
pre (v)= clock;
clock = clock +1 ;
for each edge (v,u)
do if visited (u)= false
then EXPLORE (u)
endif
endfor;
post(v)= clock;
clock = clock +1
Question 2: Consider the following directed graph:
(2.1) Draw the DFS-forest obtained by running algorithm DFS. Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS-forest, give the pre- and post-number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically first.
(2.2) Draw the DFS-forest obtained by running algorithm DFS. Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS-forest, give the pre- and post-number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically last.
Note that in (2.1) algorithm DFS(G) starts by calling Explore(A), Explore for vertex A.
Note that in (2.2) algorithm DFS(G) starts by calling Explore(G), Explore for vertex G.
Algorithm DFS(G) :
for each vertex v
do visited(v)= false
endfor;
clock =1;
for each vertex v
do if visited(v)= false
then ExPLORE(v)
endif
endfor
Algorithm EXPLORE (v) :
visited(v)= true;
pre(v)= clock;
clock = clock +1 ;
for each edge (v,u)
do if visited (u)= false
then ExplorE(u)
endif
endfor;
post(v)= clock;
clock = clock +1
image text in transcribed

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database And Expert Systems Applications 15th International Conference Dexa 2004 Zaragoza Spain August 30 September 3 2004 Proceedings Lncs 3180

Authors: Fernando Galindo ,Makoto Takizawa ,Roland Traunmuller

2004th Edition

3540229361, 978-3540229360

More Books

Students also viewed these Databases questions

Question

explain what is meant by the terms unitarism and pluralism

Answered: 1 week ago