Consider the graph and its adjacency list representation given in Page 559 of the textbook. Show a trace of DFS on this graph starting with vertex 0 by showing the contents of the arrays, marked[], EdgeTo[], and id[] during its execution. Show the DFS spanning forest constructed at the end of the algorithm. Assume that the DFS continues by picking the smallest unmarked vertex until all vertices are visited.
Consider the graph and its adjacency list representation given in Page 559 of the textbook. Show a trace of BFS on this graph starting with vertex 0 by showing the contents of the arrays, marked[], EdgeTo[] during its execution. Show the BFS spanning forest constructed at the end of the algorithm. Assume that the BFS continues by picking the smallest unmarked vertex until all vertices are visited.
Prove that every connected graph has a vertex whose removal (including all adjacent edges) will not disconnect the graph by describing a DFS method that nds such a vertex.
Design a BFS based algorithm to compute the girth of a bipartite graph. The girth of a graph is the length of its shortest cycle.
Design an algorithm to determine whether a DAG has a Hamiltonian path. A path in a directed graph is called Hamiltonian if it visits each vertex exactly once.
1
