Can you explain the logic behind question 3

(a) Draw the DFS tree for this graph, starting from node A. Assume that DFS traverses nodes in (b) Draw the BFS tree for this graph, starting from node A. Assume that BFS traverses nodes in alphabetic order. (That is, if it could go to either B or C, it will always choose B first). alphabetic order. (That is, if it could go to either B or C, it will always choose B first). Give an algorithm to detect whether a given undirected graph G -(V,E) contains a cycle. Prove that your algorithm is correct (i.e., if there is a cycle it will output one and if not it will say there Problem 2: Cycle Detection is no cycle). The running time of your algorithm should be O(VI+IE) Problem 3: Depth First Search ancestor in the DFS-tree as a back edge. Either prove the following statement or provide a counter-example: if G is an undirected, connected graph, then each of its edges is either in the depth-first search tree or is a back edge. (a) During the execution of depth first search, we refer to an edge that connects a vertex to an is called a bridge. Either prove the following statement or provide a counter-example: every bridge e must be an edge in a depth-first search tree of G. (b) Suppose G is a connected undirected graph. An edge whose removal disconnects the graph Problem 4: DFS for DAGs During Spring Break, Emilie's grandmother taught her how make lemon-mering returning, Emilie can remember all the steps she needs to perform, but unfortunately, she ue pie. Upon You do not need to turn in these problems. The goali quiz that will cover the same or similar problems. proble Problem 1: Odd Cycle Detection Given an undirected graph G- (V,E), design au algorithm tha a cycle of odd length. Prove its correctness. Your algorithm sh Problem 2: BFS Shortest Path Suppose that you want you would