Prove that a depthfirst search reaches all vertices in an un

Prove that a depth-first search reaches all vertices in an undirected connected graph. Repeat part (a) for breadth-first search.

Solution

Depth-first search, or DFS, is a way to traverse the graph.

Algorithm

In DFS, each vertex has three possible colors representing its state:

white: vertex is unvisited;

gray: vertex is in progress;

black: DFS has finished processing the vertex.

NB. For most algorithms boolean classification unvisited / visited is quite enough, but we show general case here.

Initially all vertices are white (unvisited). DFS starts in arbitrary vertex and runs as follows:

1.     Mark vertex u as gray (visited).

2.     For each edge (u, v), where u is white, run depth-first search for u recursively.

3.     Mark vertex u as black and backtrack to the parent.

Example. Traverse a graph shown below, using DFS. Start from a vertex with number 1.

Source graph.

Mark a vertex 1 as gray.

There is an edge (1, 4) and a vertex 4 is unvisited. Go there.

Mark the vertex 4 as gray.

There is an edge (4, 2) and vertex a 2 is unvisited. Go there.

Mark the vertex 2 as gray.

There is an edge (2, 5) and a vertex 5 is unvisited. Go there.

Mark the vertex 5 as gray.

There is an edge (5, 3) and a vertex 3 is unvisited. Go there.

Mark the vertex 3 as gray.

There are no ways to go from the vertex 3. Mark it as black and backtrack to the vertex 5.

There is an edge (5, 4), but the vertex 4 is gray.

There are no ways to go from the vertex 5. Mark it as black and backtrack to the vertex 2.

There are no more edges, adjacent to vertex 2. Mark it as black and backtrack to the vertex 4.

There is an edge (4, 5), but the vertex 5 is black.

There are no more edges, adjacent to the vertex 4. Mark it as black and backtrack to the vertex 1.

There are no more edges, adjacent to the vertex 1. Mark it as black. DFS is over.

As you can see from the example, DFS doesn\'t go through all edges. The vertices and edges, which depth-first search has visited is a tree. This tree contains all vertices of the graph (if it is connected) and is called graph spanning tree. This tree exactly corresponds to the recursive calls of DFS.

BFS

a

(b, c, d, e)

b

(a, d, e)

c

(a, f, g)

d

(a, b, e)

e

(a, b, d)

f

(c, g)

g

(c, f)

	Source graph.
	Mark a vertex 1 as gray.
	There is an edge (1, 4) and a vertex 4 is unvisited. Go there.
	Mark the vertex 4 as gray.
	There is an edge (4, 2) and vertex a 2 is unvisited. Go there.
	Mark the vertex 2 as gray.
	There is an edge (2, 5) and a vertex 5 is unvisited. Go there.
	Mark the vertex 5 as gray.
	There is an edge (5, 3) and a vertex 3 is unvisited. Go there.
	Mark the vertex 3 as gray.
	There are no ways to go from the vertex 3. Mark it as black and backtrack to the vertex 5.
	There is an edge (5, 4), but the vertex 4 is gray.
	There are no ways to go from the vertex 5. Mark it as black and backtrack to the vertex 2.
	There are no more edges, adjacent to vertex 2. Mark it as black and backtrack to the vertex 4.
	There is an edge (4, 5), but the vertex 5 is black.
	There are no more edges, adjacent to the vertex 4. Mark it as black and backtrack to the vertex 1.
	There are no more edges, adjacent to the vertex 1. Mark it as black. DFS is over.