BFS and DFS Example: Traversal Algorithms in Graphs

Want to go from beginner to advanced in DSA? 

Explore Uncodemy’s Data Structures Course interactive learning, real projects, and interview-ready concepts. 

 What Are Graphs in DSA? 

Imagine a network of cities connected by roads. Each city is a node (vertex), and the road connecting two cities is an edge. That’s a graph. 

Now, how do you explore all the cities in a smart way? That’s where graph traversal comes into play. 

The two most common algorithms to explore graphs: 

• BFS (Breadth-First Search) 
• DFS (Depth-First Search) 

Let’s break them down with real, working examples. 

 BFS (Breadth-First Search) with Example 

How BFS Works: 

BFS starts from a node and explores all immediate neighbors first, before moving deeper into the graph. 

It uses a Queue (FIFO) data structure. 

Real-Life Analogy: 

Imagine spreading a rumor in a classroom. You tell your first-row friends. Then they tell their friends in the next row. The rumor spreads level by level that’s BFS! 

 BFS Algorithm (Steps): 

1. Start from a source node. 

2. Add it to the queue. 

3. Mark it as visited. 

4. While the queue is not empty: 

• Remove the first node. 
• Add all its unvisited neighbors to the queue. 
• Mark them as visited. 

 BFS Example Graph: 

   0 

  / \ 

 1   2 

 |   | 

 3   4 

 BFS C Code Example: 

#include <stdio.h> 

#include <stdlib.h> 

#define SIZE 5 

int visited[SIZE] = {0}; 

int queue[SIZE], front = 0, rear = -1; 

void enqueue(int value) { 

    queue[++rear] = value; 

} 

int dequeue() { 

    return queue[front++]; 

} 

void bfs(int graph[SIZE][SIZE], int start) { 

    visited[start] = 1; 

    enqueue(start); 

    while (front <= rear) { 

        int current = dequeue(); 

        printf("%d ", current); 

        for (int i = 0; i < SIZE; i++) { 

            if (graph[current][i] && !visited[i]) { 

                enqueue(i); 

                visited[i] = 1; 

            } 

        } 

    } 

} 

int main() { 

    int graph[SIZE][SIZE] = { 

        {0,1,1,0,0}, 

        {1,0,0,1,0}, 

        {1,0,0,0,1}, 

        {0,1,0,0,0}, 

        {0,0,1,0,0} 

    }; 

    printf("BFS Traversal: "); 

    bfs(graph, 0); 

    return 0; 

}

Output: 

BFS Traversal: 0 1 2 3 4 

DFS (Depth-First Search) with Example 

 How DFS Works: 

DFS starts from a node, explores as deep as possible along a branch, then backtracks. 

It uses Stack (LIFO) or recursion. 

Real-Life Analogy: 

Think of exploring a maze you go forward until you hit a wall, then backtrack and try a new path. That’s DFS! 

DFS Algorithm (Steps): 

1. Start from a source node. 

2. Mark it as visited. 

3. Explore each unvisited neighbor recursively. 

4. Backtrack when needed. 

DFS C Code Example: 

#include <stdio.h> 

#define SIZE 5 

int visited[SIZE] = {0}; 

void dfs(int graph[SIZE][SIZE], int node) { 

    visited[node] = 1; 

    printf("%d ", node); 

    for (int i = 0; i < SIZE; i++) { 

        if (graph[node][i] && !visited[i]) { 

            dfs(graph, i); 

        } 

    } 

} 

int main() { 

    int graph[SIZE][SIZE] = { 

        {0,1,1,0,0}, 

        {1,0,0,1,0}, 

        {1,0,0,0,1}, 

        {0,1,0,0,0}, 

        {0,0,1,0,0} 

    }; 

    printf("DFS Traversal: "); 

    dfs(graph, 0); 

    return 0; 

}

 Output: 

DFS Traversal: 0 1 3 2 4 

 BFS vs DFS: Quick Comparison 

Where BFS and DFS Are Used 

 Interview Tip 

“How do you detect a cycle in a directed graph?” 

Answer: Use DFS with recursion stack tracking. 

“How to find shortest distance between two nodes?” 

Answer: Use BFS it guarantees the shortest path in unweighted graphs. 

 How to Practice BFS and DFS 

Try solving problems on: 

• LeetCode (Problems: 102, 200, 207) 
• HackerRank Graph section 
• GFG BFS & DFS practice sets 

Frequently Asked Questions (FAQs) 

Q1. Which is better: BFS or DFS? 

Depends on the problem. Use BFS for shortest paths; use DFS for exploring all paths. 

Q2. Can DFS be implemented iteratively? 

Yes, using a stack instead of recursion. 

Q3. Does DFS or BFS use more memory? 

BFS usually uses more memory because it stores all neighbors at each level. 

Q4. Are BFS and DFS only for graphs? 

Nope. Trees, grids, mazes anything with nodes and connections. 

Q5. Can BFS and DFS fail? 

They can loop infinitely if you forget to mark nodes as visited. Always handle that. 

Final Thoughts 

Whether you’re prepping for a coding interview or just trying to level up your DSA game, understanding BFS and DFS with actual examples is essential. They’re more than just theory they’re part of your problem-solving toolbox.