Consider the graphs on the right, which we denote as a cycle and an in- finite...

 

Transcribed Image Text:

Consider the graphs on the right, which we denote as a cycle and an in- finite diamond strip (IDS). The cycle has n nodes V1, Unvo that are consecutively ordered, i.e., vi has vi-1 and vi+1 mod n as its two neigh- bors, with v-1 before Vi+1 mod n. The IDS extends infinitely to both left and right. For any node in the IDS, assume that in its adjacency list, the neighbors on the left appear before the neighbors on the right. Now consider running BFS and DFS tree and graph searches on these two graphs. For the cycle graph, suppose the start node is x1 = v and the goal node is xG = xk, 1kn. For the diamond strip, the distance between x1 (i.e., the green node) and xG (i.e., the red node) is 2m. For each of the eight search combinations, provide your estimate (i.e., in big O(-) notation) of the number of nodes that has been added to the queue when the search is complete. If you think that the search does not end, the answer should be infinity. Briefly justify your answer. Consider the graphs on the right, which we denote as a cycle and an in- finite diamond strip (IDS). The cycle has n nodes V1, Unvo that are consecutively ordered, i.e., vi has vi-1 and vi+1 mod n as its two neigh- bors, with v-1 before Vi+1 mod n. The IDS extends infinitely to both left and right. For any node in the IDS, assume that in its adjacency list, the neighbors on the left appear before the neighbors on the right. Now consider running BFS and DFS tree and graph searches on these two graphs. For the cycle graph, suppose the start node is x1 = v and the goal node is xG = xk, 1kn. For the diamond strip, the distance between x1 (i.e., the green node) and xG (i.e., the red node) is 2m. For each of the eight search combinations, provide your estimate (i.e., in big O(-) notation) of the number of nodes that has been added to the queue when the search is complete. If you think that the search does not end, the answer should be infinity. Briefly justify your answer.