Graph Depth First Search in Java, easy in 5 minutes

The post shows you Graph Depth First Search in Java. Depth First Search or Depth First Traversal is a recursive algorithm for visiting all the vertices of a graph or tree data structure. Here, there is different a bit between the implementation of Depth First Search and Breadth First Search algorithm. Let’s dive into it.

Graph Depth First Search in Java

Depth First Search (DFS) Algorithm

When visiting a graph from a vertex to another vertex, you maybe get loops so a vertex might be visited again. Here, we can fix it by using a flag of boolean type to mark a visited vertex. It’s not same as Breadth First Search, we use a stack to store vertices that need to visited here.

Graph Depth First Search in Java

The Depth First Search Algorithm works as follows:

  1. Push a vertex of the graph on top of a stack.
  2. Pop the top item of the stack and mark it as visited.
  3. Create a list of that vertex’s adjacent nodes. Then just add the ones which aren’t visited on the top of the stack.
  4. Keep repeating steps 2 and 3 until the stack is empty.
Depth First Search Algorithm pseudocode

Time and space complexity

The time complexity can be expressed as O(V + E), V is the number of vertices and E is the number of edges in the graph since every vertex and every edge will be explored in the worst case.

The space complexity can be expressed as O(V).

Implement of DFS

Now, you can implement a Graph Depth First Search in Java looks like this program

Here is output

 

That’s all about Graph Depth First Search in Java.

References

Graph Data Structure in Java


Graph documentation

Please share it if you found this useful
Hide Buttons