In the previous article we already discussed the BFS(Breadth First Search) Algorithm. Now in this article we are going to take a tour of the DFS algorithm known as Depth First Search Algorithm. A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Tremaux as a strategy for solving mazes. Let’s start our journey.

DFS (Depth First Search) Algorithm

DFS Algorithm stands for Depth First Search Algorithm. It is a technique used to explore and traverse graphs or trees. It starts from a specific node (or vertex) in the graph and explores as far as possible along each branch before backtracking. In other words, DFS will first explore all the nodes that are directly connected to the source node. After that, it will move on to exploring the nodes that are indirectly connected to the source node. It is an uninformed search technique. It used a stack data structure based on (LIFO) principle.

Example

Imagine you’re in a maze, and you want to find your way from the starting point to an exit. Instead of planning out a specific route beforehand, you decide to explore the maze by following a simple strategy: whenever you reach a new intersection, you always choose a path that you haven’t taken before. And if you hit a dead end, you backtrack to the last intersection and try a different path.

How DFS Works?

DFS works similarly. It’s a method used to explore and navigate through graphs or trees. Here’s how it works:

1. Start at a node: You begin at a particular node (or point) in the graph or tree.
2. Explore: From that starting node, you pick one of its neighbors that you haven’t visited yet, and you move to that neighbor.
3. Keep going deeper: You keep repeating step 2 for the new node you just reached. In other words, you keep exploring as far down a branch as you can before backtracking.
4. Backtrack: If you reach a point where you can’t go any further (i.e., you hit a dead end), you backtrack to the previous node you came from. This is like retracing your steps back to the last intersection in the maze.
5. Repeat: You then repeat steps 2-4 for the other unexplored branches until you’ve visited all reachable nodes.

Steps for DFS

Step1 – As you can observe in the above image, our initial stack and visited arrays remain null.

Step2 – Now we visit 9 and place its unvisited adjacent nodes into the stack.

Step3 – Now, with Node 0 at the top of the stack, we visit node 0, remove it from the stack, and add all its unvisited adjacent nodes to the stack..

Step-4 – Now, with Node 5 at the stack’s top, we visit node 5, remove it from the stack, and place all its unvisited adjacent nodes (i.e., 3, 7) into the stack.

Step5 – Now, with Node 3 at the top of the stack, we visit node 3, remove it from the stack, and place all its unvisited adjacent nodes into the stack.

Step6 – Now, with Node 7 at the stack’s top, we visit node 7, remove it from the stack, and add all its unvisited adjacent nodes to the stack.

Now, the stack becomes empty, indicating that we have visited all the nodes and our DFS traversal concludes.

Python Code Using DFS Algorithm

Here’s a simple example of Depth-First Search (DFS) algorithm implemented in Python:

# Example graph represented as an adjacency list
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1, 6],
5: [2],
6: [4]
}

def dfs(graph, node, visited):
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)

# Initialize a set to keep track of visited nodes
visited_nodes = set()

# Start DFS from a particular node
start_node = 0
print("DFS traversal starting from node", start_node)
dfs(graph, start_node, visited_nodes)

JAVA Code Using DFS Algorithm

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DFSAlgorithm {

static class Graph {
private int vertices;
private List<List<Integer>> adjacencyList;

public Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}

public void addEdge(int source, int destination) {
adjacencyList.get(source).add(destination);
}

public void dfs(int startNode, Set<Integer> visited) {
System.out.print(startNode + " ");
visited.add(startNode);

for (int neighbor : adjacencyList.get(startNode)) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
}

public static void main(String[] args) {
int vertices = 7;
Graph graph = new Graph(vertices);

graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(4, 6);

int startNode = 0;
Set<Integer> visitedNodes = new HashSet<>();

System.out.println("DFS traversal starting from node " + startNode);
graph.dfs(startNode, visitedNodes);
}
}

Replace the edges added to the graph with your graph’s edges. This Java code defines a Graph class and implements DFS traversal on it.

Learn more about DFS & its Pseudocode

Thanks for reading.

Anshul Pal

Hey there, I’m Anshul Pal, a tech blogger and Computer Science graduate. I’m passionate about exploring tech-related topics and sharing the knowledge I’ve acquired. With two years of industry expertise in blogging and content writing, I’m also the co-founder of HVM Smart Solution. Thanks for reading my blog – Happy Learning!