Java Reference
In-Depth Information
3
for
each neighbor w of v
4
if
(w has not been visited) {
5 set v as the parent for w in the tree;
6 dfs(w);
7 }
8 }
check a neighbor
recursive search
You can use an array named
isVisited
to denote whether a vertex has been visited.
Initially,
isVisited[i]
is
false
for each vertex
i
. Once a vertex, say
v
, is visited,
isVisited[v]
is set to
true
.
Consider the graph in Figure 28.12a. Suppose we start the depth-first search from vertex
0. First visit
0
, then any of its neighbors, say 1. Now
1
is visited, as shown in Figure 28.12b.
Vertex 1 has three neighbors—0, 2, and 4. Since 0 has already been visited, you will visit
either 2 or 4. Let us pick 2. Now
2
is visited, as shown in Figure 28.12c. Vertex 2 has three
neighbors: 0, 1, and 3. Since 0 and 1 have already been visited, pick 3.
3
is now visited, as
shown in Figure 28.12d. At this point, the vertices have been visited in this order:
0
,
1
,
2
,
3
Since all the neighbors of 3 have been visited, backtrack to 2. Since all the vertices of 2
have been visited, backtrack to 1. 4 is adjacent to 1, but 4 has not been visited. Therefore, visit
4
, as shown in Figure 28.12e. Since all the neighbors of 4 have been visited, backtrack to 1.
Since all the neighbors of 1 have been visited, backtrack to 0. Since all the neighbors of 0 have
been visited, the search ends.
Since each edge and each vertex is visited only once, the time complexity of the
dfs
method is
O(|E| + |V|)
, where
|E|
denotes the number of edges and
|V|
the number of
vertices.
DFS time complexity
0
1
0
1
0
1
2
2
2
3
4
3
4
3
4
(a)
(b)
(c)
0
1
0
1
2
2
3
4
3
4
(d)
(e)
F
IGURE
28.12
Depth-first search visits a node and its neighbors recursively.
28.7.2 Implementation of Depth-First Search
The algorithm for DFS in Listing 28.8 uses recursion. It is natural to use recursion to imple-
ment it. Alternatively, you can use a stack (see Programming Exercise 28.3).
Search WWH ::
Custom Search