Given a graph G and the Breadth First Search (BFS) and Depth First Search (DFS)
ID: 3914985 • Letter: G
Question
Given a graph G and the Breadth First Search (BFS) and Depth First Search (DFS) traversal algorithms as follows:
2.A.) (10 POINTS) Assume that node 1 wants to reach node 7 in graph G by using the Breadth First Search (BFS) traversal algorithm. Also assume that if there is a possibility of more than one paths to take during traversal, the algorithm will choose the leftmost node. How many number of nodes (starting from node 1 ending at node 7) need to be visited via this traversal? Run the BFS traversal algorithm to show your step by step work. You need to show your work to get credit for this question.
2.B.) (10 POINTS) Assume that node 1 wants to reach node 7 in graph G by using the Depth First Search (DFS) traversal algorithm. Also assume that if there is a possibility of more than one paths to take during traversal, the algorithm will choose the leftmost node. How many number of nodes (starting from node 1 ending at node 7) need to be visited via this traversal? Run the DFS traversal algorithm to show your step by step work. You need to show your work to get credit for this question.
2.C.) (10 POINTS) Compare the results you have obtained in 2A and 2B. Which traversal requires visiting more steps? Why? Please explain.
BFSIG ) 2colorWHITE 2 5 o whik 10 12 kr each v € GA411 12 13 16 18 ·.cokr = BLACK DFS-VIsIT(G,) DFS(G) I for each vertex u eG.V 2 .color- WHITE time = time+ 1 2 u.dtim u.colorGRAY time =0 for each vertex u e G.V for each ve G.Adl 5 if w.colorWHITE 5 ifu.color ## wHITE DFS-VISIT(G DFS-VISIT(G) 8u.colorBLACK 9 time = time +1 10 u,f=timeExplanation / Answer
2.a) BFS: Goes and searches level by level
In Queue : 1
In Queue : 2 3
In Queue : 3 4 5
In Queue : 4 5 6
In Queue : 5 6 7
Total number of vertices visited are 7
2.b) DFS: Searches through the depth
From top of the Stack: 1
From top of the Stack: 2 1
From top of the Stack: 4 2 1
From top of the Stack: 7 4 2 1
Total number of vertices visited are 4
2.c) BFS required more for this graph and given vertices since BFS visited 7 vertices and DFS did just 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.