Let G be an undirected graph whose vertices are integers 1 through 8, and let th

Question

Let G be an undirected graph whose vertices are integers 1 through 8, and let the adjacent vertices of each vertex be given by the table below: Assume that, in a traversal of G, the adjacent lists of each vertex are given as shown in the table above. Give the sequence of vertices of G visited during a Depth-First Search (DFS) traversal starting at vertex 1. Give the list of edges that are marked "discovery" and the list of edges marked "back". Give the sequence of vertices of G visited during a Breadth-First Search (BFS) traversal starting at vertex 1. Give the lists L_i produced by the algorithm. Give the lists of edges that are marked "discovery" and the list of edges marked "cross".

Explanation / Answer

DFS sequence: 1 2 3 5 6 8 4 7

discovery edge: 1-2 ,2-3 , 3-5 , 5-6 , 6-8 , 8-4 , 4-7

back edge: 3-1 , 5-2 , 6-1 , 6-2 , 6-3,8-1, 8-2, .....

BFS sequence: 1 3 2 4 5 6 7 8

discovery edge: 1-2, 1-3, 3-4,3-5,3-6 ....

cross edge: 2-3, 4-5 ,5-6

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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