Consider the following two graphs: Run the breadth-first search algorithm on the undirected graph G1, starting from vertex 1 , and show its final output. When you have to choose which vertex to process next (and that choice is not otherwise specified by the BFS algorithm), use the one with the smallest label. Draw the tree edges with solid lines and the non-tree edges with dashed lines. Indicate the layers of the BFS tree. Is G1 bipartite? Justify your answer with reference to the BFS tree. Repeat part (a) on the directed graph G2. Run the depth-first search algorithm on the undirected graph G1, starting from vertex 1 , and show its final output. When you have to choose which vertex to process next (and that choice is not otherwise specified by the DFS algorithm), use the one with the smallest label. Repeat part (d) on the directed graph G2. Is G2 strongly connected? Justify your answer with reference to a search tree (or trees)