Depth First Search

 |  WORDS: 433 | Time: 3 Mins
AlgorithmSearch
Algorithm, C++, Graph

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.

Undirected Graphs

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

Step Diagram

Steps:

  1. Access to A.
  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.
  3. Access to B. Because B before D, first visit B.
  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.
  5. Access to F. All adjacency point of B and C are accessed, so return to A and access to next adjaceny point of A.
  6. Access to G.
  7. Access to E.

C++ Implememtation

Adjacency Matrix Version
1
// Work in progress
Adjacency List Version
1
// Work in progress

Depth first search for directed graphs

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

Directed Graphs

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

Step Diagram

Steps:

  1. Access to A.
  2. Access to B. After visiting A, the next vertex to which A should go is the vertex B that should be accessed next.
  3. Access to C. After visiting B, what should be followed is another vertex of B’s out-edge. Because C is the first one, so first visit it
  4. Access to E. Next to the other vertex of the out-edge of the C vertex.
  5. Access to D. Then visit the other vertices of E’s out edge, vertices B and D. Vertex B has already been visited, so visit vertex D.
  6. Access to F.
  7. Access to G.

C++ Implememtation

Adjacency Matrix Version
1
// Work in progress
Adjacency List Version
1
// Work in progress
Share