Practice problem: use DFS version of topological sort for the following DAG J6 DFS(G) I for each vertex u e G. V J1 J2 (J5 J7 u.color = WHITE u.A = NIL 4 time = 0 5 for each vertex u e G. V 6. if u.color == WHITE DFS-VISIT (G, u) J3 J4 DFS-VISIT (G. u) 1 time = time +1 2 u.d = time 3 u.color = GRAY 4 for each v eG.Adj[u] TOPOLOGICAL-SORT(G) 1 call DFS(G) to compute finishing times v.f for each vertex v 2 as each vertex is finished, insert it onto the front of a linked list 5 if v.color == WHITE v.A = u 7 DFS-VISIT (G, v) 8 u.color = BLACK 9 time = time +1 return the linked list of vertices 10 u.f = time
Practice problem: use DFS version of topological sort for the following DAG J6 DFS(G) I for each vertex u e G. V J1 J2 (J5 J7 u.color = WHITE u.A = NIL 4 time = 0 5 for each vertex u e G. V 6. if u.color == WHITE DFS-VISIT (G, u) J3 J4 DFS-VISIT (G. u) 1 time = time +1 2 u.d = time 3 u.color = GRAY 4 for each v eG.Adj[u] TOPOLOGICAL-SORT(G) 1 call DFS(G) to compute finishing times v.f for each vertex v 2 as each vertex is finished, insert it onto the front of a linked list 5 if v.color == WHITE v.A = u 7 DFS-VISIT (G, v) 8 u.color = BLACK 9 time = time +1 return the linked list of vertices 10 u.f = time
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Use DFS version of topological sort for the following DAG
![Practice problem: use DFS version of topological sort for the following
DAG
DFS(G)
J6
1
for each vertex u e G. V
J1
J2
(J5
J7
2
u.color = WHITE
3
u.N = NIL
4 time = 0
5 for each vertex u e G. V
if u.color == WHITE
DFS-VISIT (G, u)
J3
J4
7
DFS-VISIT (G, u)
time = time +1
1
2 u.d = time
TOPOLOGICAL-SORT(G)
3
u.color = GRAY
4 for each v e G.Adj[u]
1 call DFS(G) to compute finishing times v.f for each vertex v
2 as each vertex is finished, insert it onto the front of a linked list
if v.color == WHITE
v.A = u
DFS-VISIT (G, v)
8 u.color = BLACK
9 time = time + 1
10 u.f = time
3 return the linked list of vertices](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F519f9fec-10ec-4a75-90d9-e77336a95d5f%2F6996e5ea-9a55-4d15-a382-74d81b3ecca7%2Fvp1i0et_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Practice problem: use DFS version of topological sort for the following
DAG
DFS(G)
J6
1
for each vertex u e G. V
J1
J2
(J5
J7
2
u.color = WHITE
3
u.N = NIL
4 time = 0
5 for each vertex u e G. V
if u.color == WHITE
DFS-VISIT (G, u)
J3
J4
7
DFS-VISIT (G, u)
time = time +1
1
2 u.d = time
TOPOLOGICAL-SORT(G)
3
u.color = GRAY
4 for each v e G.Adj[u]
1 call DFS(G) to compute finishing times v.f for each vertex v
2 as each vertex is finished, insert it onto the front of a linked list
if v.color == WHITE
v.A = u
DFS-VISIT (G, v)
8 u.color = BLACK
9 time = time + 1
10 u.f = time
3 return the linked list of vertices
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 4 steps with 4 images
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education