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:

Starting node: 0

BFS Traversal Order

0 → 1 → 2 → 3 → 4

BFS Step-by-Step Explanation

Steps:

Create a queue
Mark the starting node as visited
Push it into the queue
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:

Start from a node
Mark it as visited
Visit first unvisited neighbor
Repeat recursively
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.