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

Assume that the graph is represented using a adjacency matrix so that you iterate through the vertices adjacent to v 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.