Understanding the Problem
We are given a graph with a set of nodes and edges. The task is to traverse the graph using the Depth-First Search (DFS) algorithm. DFS explores as far as possible along each branch before backtracking, ensuring that each node is visited once.
This traversal technique is foundational for many graph problems like counting connected components, detecting cycles, and solving maze-like puzzles. In this lesson, we will understand how DFS works step-by-step and apply it to a practical example with beginner-friendly explanations.
Step-by-Step Solution with Example
Step 1: Define the Graph
Let's take a sample undirected graph represented as an adjacency list:
{
0: [1, 2],
1: [0, 3],
2: [0],
3: [1, 4],
4: [3]
}
This graph has 5 nodes. The connections (edges) between nodes are undirected, meaning you can go both ways along the edge. For example, 0 is connected to 1 and 2, and 1 is connected back to 0 and to 3.
Step 2: Understand the DFS Approach
DFS starts at a node (say, node 0), marks it as visited, and then recursively explores each unvisited neighbor. Once all neighbors are visited, it backtracks.
We use a visited
array or set to keep track of nodes we have already seen, to avoid visiting the same node again and getting stuck in cycles.
Step 3: Implement the DFS Logic
Here’s a basic recursive DFS implementation:
function dfs(node, visited, graph) {
visited[node] = true;
console.log("Visited", node);
for (let neighbor of graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
Step 4: Apply DFS to the Graph
We start from node 0 and visit its neighbors one by one. Here's how it works:
- Visit node 0 ➝ mark as visited
- From 0, go to node 1 ➝ mark 1 visited
- From 1, go to node 3 ➝ mark 3 visited
- From 3, go to node 4 ➝ mark 4 visited
- Backtrack to 3 ➝ 1 ➝ 0
- From 0, go to node 2 ➝ mark 2 visited
All nodes are now visited.
Step 5: Visualize the Order
The order of traversal will be: 0 → 1 → 3 → 4 → 2
Edge Cases
Disconnected Graph
If the graph is disconnected (e.g., two separate subgraphs), starting DFS from one node will not visit all nodes. In such cases, we run DFS for every unvisited node in a loop:
for (let node in graph) {
if (!visited[node]) {
dfs(node, visited, graph);
}
}
Graph with Cycles
If a graph contains cycles, DFS can fall into infinite loops without a visited
check. That’s why we always verify whether a node has already been visited before calling DFS on it.
Directed Graphs
DFS logic remains the same, but it follows the direction of edges. That means if there's an edge from A → B, DFS can go from A to B, but not from B to A unless a separate edge exists.
Empty Graph
If the graph has no nodes or edges, the DFS simply ends immediately with no output. Always validate inputs before running DFS logic.
Finally
Depth-First Search is a powerful tool to explore and analyze graphs. Understanding the traversal order and marking visited nodes are the key steps to avoid infinite loops and ensure correctness. For disconnected graphs or graphs with cycles, we slightly extend the basic DFS to handle all components safely.
As you practice, try applying DFS to real-world scenarios like social networks (friend groups), map navigation (paths and roads), and puzzle solving (mazes). This will strengthen your intuition and mastery over graph traversal techniques.
Comments
Loading comments...