Depth First Search or DFS for a Graph in Java

28 Mar 2025 | 4 min read

For traversing or searching over graph structures, the basic method Depth First Search (DFS) is employed. It is a vital tool for many graph theory tasks, such as pathfinding, cycle detection, connection tests, and more, since it travels as far as feasible down each branch before turning around.

DFS uses an implicit or explicit stack that is operated upon by recursion, implementing the last-in, first-out (LIFO) principle. We will examine the DFS algorithm, its Java implementation, and its modifications in this post.

DFS Algorithm Explanation

The DFS algorithm works as follows:

Start at a node (usually the root or any arbitrary node).
Mark the node as visited and push it onto the stack or use recursion.
Explore the adjacent nodes of the current node that haven't been visited yet.
Recursively apply DFS to each adjacent node until there are no more nodes to visit.
If a node leads to a dead end (all adjacent nodes have been visited), backtrack to the previous node.
Repeat until all nodes are visited.

Let's implement the above algorithm in a Java program.

File Name: DfsInGraph.java

Output:

 
Depth First Search starting from vertex 0:
0 1 3 4 2 5

Explanation

An adjacency list is used by the Graph class to represent the graph. Every vertex possesses an array called LinkedList[] that contains a list of its neighbours. The addEdge() function creates edges connecting two vertices.

Edges are added in both directions, from w to v and from vertex v to w, because we are working with an undirected graph. To keep track of which vertices have previously been visited, the DFS() function initialises a boolean array visited[].

The real recursive traversal is then handled by a helper function called DFSUtil().The current node is marked as visited and printed using the DFSUtil() function. Next, it investigates every one of the current node's unexplored neighbours recursively.

Complexity Analysis

Time Complexity: Based on the number of vertices (V) and edges (E), the time complexity of DFS is O(V + E). This is a result of the traverse processing each vertex and edge once.

Space Complexity: Because of the recursive call stack, the storage required for the visited[] array, the adjacency list, and other components, the space complexity is O(V).

Applications of DFS

Maze Solving and Pathfinding: DFS is utilised in pathfinding algorithms when we have to solve mazes or discover all pathways in an organised way.
Cycle Detection: DFS is useful for finding cycles in graphs that are either directed or undirected. A cycle is present if a back edge is discovered during traversal.
Linked Components: DFS may be used to find every linked component inside a graph, even if the graph is shown as a collection of unconnected subgraphs.

Conclusion

Due to its recursive structure, it's very helpful for cases where you need to go back and look at every potential configuration. Comprehending DFS is essential for resolving a variety of graph-related computer science issues. This article explained the workings, applications, and complexity analysis of DFS and included a full Java implementation.

Next TopicBig data Java vs Python

← prev next →