a Prove that a depth first search reaches all vertices in an

(a) Prove that a depth first search reaches all vertices in an undirected connected graph.

(b) Repeat part (a) for breadth-first search.

Solution

(a)

A Depth First Search (DFS) in an undirected graph G can be considered as someone wandering in a labyrinth with a long rope and a can of paint, so that they don’t get lost. We start at vertex “a”, tying the end of our string to the point and painting “a” so that we can mark it as “already visited”. Next we label “a” as our current vertex called u. Then we travel along any random edge (u,v). If this selected edge (u,v) takes us to an “already visited” vertex v we return to u. And if vertex v is unvisited, we unroll our string and move to v, paint v “Already visited” and then we set v as our current vertex, and we repeat the previous steps. Eventually, we will get to a point where all incident edges on u lead to visited vertices. Therefore, in Depth First Search, we reach to all the vertices to an undirected graph.

(b)

In Breadth First Search (BFS) we do the same thing as we did in DFS, only this time we mark edges as already visited. The starting vertex “a” has level 0 and the string is unrolled the length of one edge, and all of the edges that are only one edge away from the anchor are said to be “Already Visited”. These edges are placed into level -1. In the second round, all the new edges that can be reached by unrolling the string 2 edges are visited and placed in level 2. This continues until every vertex has been assigned a level and hence for undirected graphs, using BFS too, one will have to visit every vertex.