In this tutorial, you will learn the Depth First Search implementation example on Graph with Java

Depth First Search (DFS)

Depth First Search is an algorithm for traversing or searching a graph. The algorithm starts at an arbitrary node and explores as far as possible along each branch before backtracking

For the above graph with 0 as the starting vertex, assuming that the left edges are chosen before the right edges, the traversing order will be 0 -> 1 -> 3 -> 2 -> 4

Implementation example

Approach

  • Using an array to track visited nodes to avoid processing a node more than once (graph may contain cycles)
  • Using a stack to track which nodes to visit next

UndirectedGraphByAdjacencyList is defined in Graph Data Structure