Discrete Mathematics for Computer Science

Connected Graphs 355

vertices and edges in different orders, but in any representation, each edge and vertex will
be visited.
First, mark all the vertices of G as "unvisited." For the next step, choose any vertex v,
and mark it as "visited." Suppose the first vertex on the adjacency list for v is w. If w is
marked "visited," do nothing with the edge that this entry represents, and proceed to exam-
ine the next vertex in the list of vertices adjacent to v. If w is marked "unvisited," use w as
a new starting point for this process. When all the edges incident to w are examined, return
to v, and examine the next unexamined vertex on v's list of adjacent vertices. The process
terminates when the procedure returns to the starting vertex and all the edges incident to
this vertex have been examined.
An example of a depth first search is shown in Figure 6.22. A depth first search en-
counters two kinds of edges. Some edges, called tree edges, join the vertex being examined
to a vertex that has not already been visited. All other edges incident to the current vertex
join the current vertex to an already-visited vertex. In a depth first search, the tree edges
are shown as solid lines, and all other edges are shown as dashed lines.

a Depth First Search

h beginning at a

9 bd

d

//

Lists of e

Vertices Adjacencies h le

a b c

b a d g edge to unvisited

c a d e g vertex (tree edge)

d c b f --- edge to previously

e C f visited vertex

f e d

g b c h

h g

Figure 6.22 Depth first search starting at a.

In Figure 6.22, the search has examined the edges in the order in which they are listed

in the adjacency list.

The edges in a graph can be partitioned into two sets by the search procedure. One set

of edges consists of all the edges (v, w) for which both ends of the edge have Visited[ *] =

"visited" when the edge is examined for the first time. The other set of edges consists of all

the edges (v, w) with one end-say, v-having Visited[ v ] = "visited" and the other end

w having Visited[w] = "unvisited" when the edge is examined for the first time. All the

edges in this second set form a special subgraph called a depth first search tree. Trees are
formally defined and discussed in more detail later in this chapter, but for the search just
shown in Figure 6.22, the depth first search tree is shown in Figure 6.23.