Let G be an undirected graph whose vertices are integers 1 through 8, and let th
ID: 3574257 • Letter: L
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
Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.