# Depth First Search

Depth First Search Chinese version address

# Depth First Search

## Overview

Depth first search of the graph is similar to the preorder traversal of the tree.

Suppose that the initial state is that all the vertices in the graph are not accessed, then starting from a vertex and first access to it, nextly, the depth first search traversal from each of its non-accessed adjacency points in turn, until all the vertices that have a path to the starting vertex in the graph are accessed. If there are other vertices that are not accessed, then choose another unvisited vertex as a starting point, repeat the above process until all graph vertices have been visited.

## Diagram

### Depth first search for undirected graphs

The following is an example of undirected graph, to demonstrate the depth first search.

Depth first search of the graph above, starting with vertex A:

#### Steps:

2. Access to C. Because the vertices A,B,C,D,E,F,G are stored in order in this paper, C is in front of D and F, so visit C first.
4. Access to D. After having visited C’s adjacency point B at step 3, B has no unvisit adjacency points, thus, it returns to another adjacency point D that accesses C.

### Depth first search for directed graphs

The following is an example of directed graph, to demonstrate the depth first search.

Depth first search of the graph above, starting with vertex A: