Problem 2 [20 points]. Consider the graphs on the right, which we denote as a cy
ID: 3757255 • Letter: P
Question
Problem 2 [20 points]. Consider the graphs on the right, which we denote as a cycle and an in- finite diamond strip (IDS). The cycle has n nodes vi, ,Un-to that are consecutively ordered, ie., ti has th-1 and vi+1 mod n as its two neigh- bors, with vi-1 before vitl 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 1skn. For the diamond strip, the distance between ri (i.e., the green node) and rg (i.e, the red node) is 2m. For each of the eight search combinations, provide your estimate (i 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 cycle graph, suppose the start node is v and the goal node is ro .e, in big O)Explanation / Answer
Answer :
Lets handle the 4 cases i.e. for cycle and IDS graph and BFS and DFS search.
CASE 1: - Cycle graph with BFS search
In BFS search, all the neightbours are added into the queue and processed before the next level neighbor.
In cycle graph, each node has 2 neighbors which will be added after the node is processed. Then the node which is in front of queue will be processed first followed by node just after it in the queue. Since we are moving in circular graph, the neighbours will be processed in the queue level wise. So by the time we reach to node [v_k] from [v_l] , the node [v_{(l-k+n) ext{mod n}}] will also be in queue. Hence total elements that has been processed in queue = [2*|k-l| + 1] = O(n)
CASE 2: - Cycle graph with DFS search
Since DFS keep on processing the nodes from one level to next level till the time it reaches the end of one direction. Hence in cycle graph, the maximum nodes that will be processed before reaching [v_l] will be atmost [max(|k-l|,n-|k-l|)] = O(n)
CASE 3:- IDS graph with BFS
In BFS, since the elements are added into queue and processed one level and then next level. Also the left elements are before the right elements in adjacency list. While processing [v_l] , all its 4 neighbors will be added into the queue and then those neighbors after being processed will add maximum one element in the queue. So at any point of time maximum 4 elements will be there in queue. Since the elements are added distancewise from vertex [v_l] with nearer element will be added first after far elements. So while BFS reach from [v_l] towards [v_k] all the left neighbors of [v_l] upto [v_{l-2m}] will also be processed. So the number of nodes that has been added into queue = 2*3m + 1 = 6m+1 = O(m)
CASE 4:- IDS graph with DFS
Since the left elements are before the right elements in adjacency list and the DFS keep on going to one direction till it keep on finding the nodes and the graph is infinite from both side, so the elements processed in DFS will be infinity in this case.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.