Depth-First Search - (DFS) in Graphs - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Depth-First Search (DFS) is a popular graph traversal technique that explores as far along a branch as possible before backtracking. Starting from a node, DFS goes deep into the graph, exploring child nodes before sibling nodes.

DFS is useful for tasks like detecting cycles, pathfinding, topological sorting, and solving puzzles with backtracking.

Examples❯

Input Graph (Adjacency List) DFS Output Description
{1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}
1 → 2 → 4 → 5 → 3 Classic DFS tree with backtracking: visits 2 → 4 → 5, then backtracks to visit 3.
{1: [2, 3], 2: [1, 4], 3: [1, 5], 4: [2], 5: [3, 6], 6: [5]}
1 → 2 → 4 → 3 → 5 → 6 DFS explores left from 1 to 2 → 4, backtracks to 3 → 5 → 6. Deep tree with branching.
{1: [2, 3], 2: [1, 3, 4], 3: [1, 2], 4: [2, 5], 5: [4]}
1 → 2 → 3 → 4 → 5 Cycle between 1-2-3 handled properly; DFS continues deeper through node 4 to 5.
{1: [2], 2: [1, 3, 4], 3: [2], 4: [2, 5, 6], 5: [4], 6: [4]}
1 → 2 → 3 → 4 → 5 → 6 DFS covers a “Y”-shaped graph with multiple forks under node 4.
{0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3]}
0 → 1 → 2 → 3 → 4 Linear path graph; DFS proceeds from left to right in straight line without backtracking.

Solution❯

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:

  1. Visit node 0 ➝ mark as visited
  2. From 0, go to node 1 ➝ mark 1 visited
  3. From 1, go to node 3 ➝ mark 3 visited
  4. From 3, go to node 4 ➝ mark 4 visited
  5. Backtrack to 3 ➝ 1 ➝ 0
  6. 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.

Algorithm Steps❯

  1. Initialize a visited set.
  2. Start DFS from the given node.
  3. Mark the current node as visited and process it.
  4. Recursively (or using a stack) visit all unvisited neighbors.
  5. Repeat until all connected nodes have been visited.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#define MAX 100

int graph[MAX][MAX];
int visited[MAX];
int n;

void dfs(int node) {
  if (visited[node]) return;
  visited[node] = 1;
  printf("%d ", node);

  for (int i = 0; i < n; i++) {
    if (graph[node][i] && !visited[i]) {
      dfs(i);
    }
  }
}

int main() {
  n = 4;
  graph[0][1] = graph[1][0] = 1;
  graph[0][2] = graph[2][0] = 1;
  graph[1][3] = graph[3][1] = 1;

  printf("DFS from node 0: ");
  dfs(0);
  return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(V + E)DFS visits each node and edge once, even in the best case where traversal may end early due to no unvisited neighbors.
Average CaseO(V + E)Each node is explored once and each edge is checked once, regardless of the structure of the graph.
Worst CaseO(V + E)In the worst case, DFS explores all vertices and all edges, particularly in a densely connected graph.

Space Complexity❯

O(V)

Explanation: The space used is proportional to the number of vertices due to the visited set and the recursion stack or explicit stack used in the process.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...