Discrete Mathematics for Computer Science

356 CHAPTER 6 Graph Theory

a

ob

Od

g e

h f

Figure 6.23 Depth first search tree.

If a graph is not connected, then the process is repeated for each connected component.

The algorithm given here is intended to deal with connected graphs.

INPUT: Connected graph G = (V, E) and start vertex v0 and vertices numbered

1, ..... IvI

RESULT: Each vertex and each edge is examined

Create an array Visited with I V I positions initialized to "unvisited"

Dfs(G, vo, Visited) /* The initial call uses start vertex vo *f

Dfs(G, v, Visited)l* The recursive procedure */

Visited [v] = "visited"

for each vertex w adjacent to v do

if (Visited [w] = "unvisited") then

Dfs(G, w, Visited)

To prove Dfs is correct, we must prove that every vertex and every edge of a connected

graph G is examined when Dfs is called for any vertex of the graph. Since every adjacency

of a vertex v is examined when Dfs(G, v, Visited) is executed, we can prove that every

vertex and every edge is examined if we can prove that Dfs is executed for each vertex

of G.

Suppose for some vertex w E V that Dfs(G, w, Visited) is not executed and

Visited [w] = "unvisited" after execution of Dfs. Without loss of generality, we can as-

sume w is adjacent to a vertex v that had Dfs(G, v, Visited) executed, because the graph

is connected and Dfs(G, v, Visited) is executed. When the adjacencies of v were ex-

amined, however, Visited[w] would have been "unvisited." Therefore, Dfs(G, w, Visited)

would have been executed, and Visited [w] would have been asssigned "visited." This