COS 226 Exercises on Undirected Graphs

1. List the vertices in the order in which they are visited (for the first time) in DFS for the following undirected graph, starting from vertex 0.

0-1 1-2 1-7 2-0 2-4 3-2 3-4 4-5 4-6 4-7 5-3 5-6 7-8 8-6

For simplicity, assume that the Graph implementation always iterates through the neighbors of a vertex in increasing order.

2. Repeat question 1 for BFS. Also give the length of the shortest path (number of edges) from vertex 0 to each other vertex.