Please do the following problem so that I can make sure I have the right answer.
ID: 674689 • Letter: P
Question
Please do the following problem so that I can make sure I have the right answer. I believe the first part shown is correct. The part I'm not sure about is the sequence being visited.
Thank you!
2. (2 points) Consider the following graph. When there are multiple candidate nodes to expand, the smaller a node number (character) is, the higher priority it has to be chosen BFS KL (D (2-1) .Construct the Breadth-First Search Tree. Staring node is A Write the sequence of vertex being visited in the above Breadth-First Search.Explanation / Answer
1. The Breadth-first search tree you have done is perfect.
2. The order of vertexes visited is:
As we already know the concept of BFS, the traversal first starts at root node and then traverse the adjacent nodes associated with the root node. After visiting all the nodes that are adjacent to the root node, the traversal then goes to the node that is adjacent to the first adjacent node of root node. After visiting the adjacent nodes of first adjacent node of root node, the traversal goes to the adjacent nodes of second adjacent node of root node. The traversal continues untill all the nodes in a tree are traversed. Node is also called as vertex.
Then the traversal order will be:
The traversal first starts at the root node that is A. Then traverse the nodes that are adjacent to the root node, those are B,C,D. After taht traversal visits the nodes that are adjacent to B, that is E,F. Then the traversal goes to the nodes that are adjacent to C, those are G,H. Then goes for the nodes M which is adjacent to D.
Till now the order is A-B-C-D-E-F-G-H-
Then after, the traversal visits I which is adjacent to E, then visits J which is adjacent to F, then visits K which is adjacent to K, then visits L which is adjacent to M.
The final order is:
A-B-C-D-E-F-G-H-M-I-J-K-L