Depth-First Search (DFS)

There are two core graph exploring algorithms breadth-first search and depth-first search. Assuming that you already familiar with BFS, so – in this topic I’m going to compare these two algorithms and also I will provide my version of DFS.

The algorithm requires some initial point which will be used as a starting point, from which traversing/searching will go on. Here is a graph and let vertix “A” be a starting point.

DFS

From vertex “A” it goes as far as it possible until it reaches the leaf or it self. Once the vertex that has no successors is reached, it gets back. On the way back, if it meets nodes that were not visited then it traverses them in same way. Visually, the path can be represented as level. Thus, it explores first level, then second and so on.

Sequence of the visited nodes will be following:

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X.

Application

As I said it is a core graph algorithm, thus it has many applications, here are some of them:

  1. Topological sort.
  2. Helps to find strongly connected graphs. In such graphs every vertex is reachable from every other vertex.
  3. Can solve puzzles with one solution, such as mazes.
  4. Can detect cycle in graph.
  5. To test if a graph is bipartite.
Edge classification

The edges that traverses depth-first search can be classified into four edge categories.

  1. A tree edge is a edge that connects two vertices.

    tree_edge

  2. A Back edge, is a edge that connects vertex with its ancestor.
    back_edge2
  3. Forward edge is a opposite of the back edge.

    fwd_edge

  4. Cross edge appears between two vertices that have no ancestor/descendant relationship.

    cross_edge

 Implementation

My version of recursive and iterative DFS you can find on GitHub: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/DepthFirstSearch.java.

Time Complexity is O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.

Leave a Reply