BFS and DFS in Graph with Example

Introduction

BFS (Breadth-First Search) and DFS (Depth-First Search) are two fundamental graph traversal algorithms in Data Structures and Algorithms (DSA). These algorithms are extremely important because almost every graph problem is based on either BFS, DFS, or a combination of both.

In simple terms, graph traversal means visiting all the nodes (vertices) of a graph systematically.

What is a Graph?

A Graph is a data structure made of:

• Vertices (nodes) – points in the graph

• Edges – connections between nodes

Graphs can represent:

• Social networks

• Road maps

• Computer networks

• Dependency systems

Graphs can be directed or undirected, and weighted or unweighted.

What is Graph Traversal?

Graph traversal is the process of visiting every node of the graph exactly once (if possible).

Traversal is required for:

• Searching a node

• Finding connected components

• Detecting cycles

• Shortest path problems

The two most commonly used traversal techniques are BFS and DFS.

What is BFS (Breadth First Search)?

Breadth First Search (BFS) explores the graph level by level.

In BFS:

• We first visit all neighbors of a node

• Then move to the next level of neighbors

BFS uses a Queue data structure.

BFS Real-Life Analogy

Think of spreading news:

• First, you tell your close friends

• Then your friends tell their friends

This level-by-level spreading is similar to BFS.

BFS Example Graph

Consider this graph:

    0
   / \
  1   2
  |   |
  3   4

Starting node: 0

BFS Traversal Order

0 → 1 → 2 → 3 → 4

BFS Step-by-Step Explanation

Steps:

1. Create a queue

2. Mark the starting node as visited

3. Push it into the queue

4. While queue is not empty:

   • Remove front node

   • Visit it

   • Add all unvisited neighbors to the queue

BFS Dry Run

Queue	Visited	Output
[0]	0	0
[1,2]	0,1,2	0
[2,3]	0,1,2,3	0,1
[3,4]	0,1,2,3,4	0,1,2

BFS Code Implementation

C++ Code

void bfs(int start, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

Java Code

void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();

    visited[start] = true;
    queue.add(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

Python Code

def bfs(start, graph):
    visited = set()
    queue = [start]
    visited.add(start)

    while queue:
        node = queue.pop(0)
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

What is DFS (Depth First Search)?

Depth First Search (DFS) explores the graph by going as deep as possible before backtracking.

In DFS:

• We visit one neighbor

• Keep moving deeper until no nodes are left

• Then backtrack

DFS uses Recursion or Stack.

DFS Real-Life Analogy

Think of exploring a maze:

• You go deep into one path

• If stuck, you come back and try another path

This behavior is similar to DFS.

DFS Example Graph

Using the same graph:

DFS Traversal Order

0 → 1 → 3 → 2 → 4

DFS Step-by-Step Explanation

Steps:

1. Start from a node

2. Mark it as visited

3. Visit first unvisited neighbor

4. Repeat recursively

5. Backtrack when no neighbor exists

DFS Code Implementation

C++ Code

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

Java Code

void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

Python Code

def dfs(node, graph, visited):
    visited.add(node)
    print(node, end=" ")

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)

BFS vs DFS (Detailed Comparison)

Feature	BFS	DFS
Traversal	Level by level	Depth first
Data Structure	Queue	Stack / Recursion
Shortest Path	Yes (unweighted)	No
Memory Usage	Higher	Lower

Time and Space Complexity

• Time Complexity: O(V + E)

• Space Complexity: O(V)

Where V = vertices, E = edges.

Important Edge Cases

• Disconnected graph

• Graph with cycles

• Graph with single node

Always handle visited nodes properly.

Common Interview Questions on BFS and DFS

• Difference between BFS and DFS

• BFS for shortest path

• DFS for cycle detection

• Recursive vs iterative DFS

Summary

BFS and DFS are the backbone of graph algorithms in DSA. BFS explores graphs level by level and is best for shortest path problems, while DFS goes deep and is useful for cycle detection and connectivity problems. Understanding their working, differences, and use cases is essential for solving real-world graph problems and cracking technical interviews.