Could someone explain the breadth-first search problem in the picture below, and
ID: 3572594 • Letter: C
Question
Could someone explain the breadth-first search problem in the picture below, and help me trace it, It was started but visually I can't see it. DONT WORRY ABOUT DFS (depth-first search )problem, just the breadth first search part. See picture below
1. Graph search. (10 points) Consider the following directed graph. CA (a) Run depth-first search, starting at vertex A. Assume the adjacency lists are in lexico- graphic order. e.g., when exploring vertex E, consider E-D before E-G or H. Complete the list of vertices in preorder (the order they are first discovered by DFS). (b) Run breadth-first search, starting at vertex A. Assume the adjacency lists are in lexico- graphic order. Complete the list of vertices in the order in which they are enqueued.Explanation / Answer
Start with node A and find all the adjacent nodes to which it has links/edges.
we got 3 nodes B,D,E keep the 3 nodes in Queue and the next node is B find all the adjacent nodes that are connected from B the Queue will be B,D,E,C,F . As B is visited dequeue node B. The output will be A B.
Then consider D the next element in queue and find all the adjacent nodes. the queue will be D,E,C,F,G,H. dequeue node 'D'. the output will be A B D
consider next element i.e E and find all the adjacent nodes the queue will be E,C,F,G,H,I. dequeue node 'E'
the output will be A B D E . as all the nodes are visited we can dequeue the elements in the same order as that of queue.
The final output is : A B D E C F G H I