Depth-first search

Depth-first search (DFS) is one of the most-basic and well-known types of algorithm in graph theory. The basic idea of DFS is deceptively simple, but it can be extended to yield asymptotically optimal solutions to many important problems in graph theory. It is a type of graph search (what it means to search a graph is explained in that article).

Principles of DFS

DFS is distinguished from other graph search techniques in that, after visiting a vertex and adding its neighbours to the fringe, the next vertex to be visited is always the newest vertex on the fringe, so that as long as the visited vertex has unvisited neighbours, each neighbour is itself visited immediately. For example, suppose a graph consists of the vertices {1,2,3,4,5} and the edges {(1,2),(1,3),(2,4),(3,5)}. If we start by visiting 1, then we add vertices 2 and 3 to the fringe. Suppose that we visit 2 next. (2 and 3 could have been added in any order, so it doesn't really matter.) Then, 4 is placed on the fringe, which now consists of 3 and 4. Since 4 was necessarily added after 3, we visit 4 next. Finding that it has no neighbours, we visit 3, and finally 5.

Stack-based implementation of DFS

The basic template given at Graph search can be easily adapted for DFS:

input G
for all u ∈ V(G)
     let visited[u] = false
for each u ∈ V(G)
     if visited[u] = false
          let S be empty
          push(S,u)
          while not empty(S)
               v = pop(S)
               if visited[v] = false
                    visit v
                    visited[v] = true
                    for each w ∈ V(G) such that (v,w) ∈ E(G) and visited[w] = false
                         push(S,w)

F has been replaced by a stack, S, because a stack satisfies exactly the necessary property for DFS: the most recently added item is the first to be removed.

Recursive implementation of DFS

There is a much cleaner implementation of DFS using recursion. Notice that no matter which vertex we happen to be examining, we execute the same code. That suggests that we might be able to wrap this code in a recursive function, in which the argument is the vertex to be visited next. Also, after a particular vertex is visited, we know that we want to immediately visit any of its unvisited neighbours. We can do so by recursing on that vertex:

function DFS(u)
     if not visited[u]
          visit u
          visited[u] = true
          for each v ∈ V(G) such that (u,v) ∈ E(G)
               DFS(v)
input G
for each u ∈ V(G)
     let visited[u]=false
for each u ∈ V(G)
     DFS(u)

Note that we do not need to check if a vertex has been visited before recursing on it, because it is checked immediately after recursing.