COS 226 Exercises on Undirected Graphs

NAME:

PRECEPT:

COS 226 Exercises on Undirected Graphs

1. Give the order in which the vertices are visited (for the first time) in DFS for the following graph using a standard adjacency-matrix representation.

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 8-7

2. Repeat question 1 for BFS.

3. Give the vertex connectivity and the edge connectivity of the graph in question 1. (Provide evidence for your answers.)