BFS and DFS Algorithm with Example Explained

These algorithms help us systematically visit all the nodes in a graph and are cornerstones of computer science. In this blog, we’ll break down the theory, show you real code examples in C, and explain how they work, step by step.

Want to understand BFS and DFS in-depth with practical DSA projects? Head to Uncodemy's blog and get real-world-ready.

What is Graph Traversal?

Graph traversal means visiting all the vertices (or nodes) of a graph in a specific order. The two main ways to traverse graphs are:

• BFS (Breadth-First Search): Goes level by level.
• DFS (Depth-First Search): Goes as deep as possible before backtracking.

Let’s start with BFS.

Breadth-First Search (BFS) Algorithm

BFS explores the graph layer by layer. It starts from a node and explores all its neighbors before moving to the next level of nodes.

Steps in BFS:

1. Pick a starting node and mark it as visited.

2. Enqueue it (add it to the queue).

3. While the queue is not empty:

• Dequeue a node.
• Visit all its unvisited neighbors and enqueue them.

C Code Example: BFS

#include <stdio.h>

#include <stdlib.h>

#define SIZE 100

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

int visited[SIZE] = {0};

void enqueue(int vertex) {

    if (rear == SIZE - 1) return;

    if (front == -1) front = 0;

    queue[++rear] = vertex;

}

int dequeue() {

    if (front == -1 || front > rear) return -1;

    return queue[front++];

}

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

    enqueue(start);

    visited[start] = 1;

    while (front <= rear) {

        int current = dequeue();

       printf("%d ", current);

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

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

               enqueue(i);

               visited[i] = 1;

            }

        }

    }

}

Depth-First Search (DFS) Algorithm

DFS dives deep into one branch before backtracking. Think of it as exploring a maze: go down one path until you can't, then return and try another.

Steps in DFS:

1. Start from the root (or any arbitrary node).

2. Mark it visited.

3. Visit an unvisited neighbor.

4. Repeat until all nodes are visited, using recursion or a stack.

• Shortest path in unweighted graphs
• GPS navigation
• Web crawlers
• Cycle detection
• Topological sorting
• Puzzle and maze solving

C Code Example: DFS

#include <stdio.h>

int visitedDFS[SIZE] = {0};

void dfs(int graph[SIZE][SIZE], int vertex, int vertices) {

    visitedDFS[vertex] = 1;

    printf("%d ", vertex);

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

        if (graph[vertex][i] && !visitedDFS[i]) {

            dfs(graph, i, vertices);

        }

    }

}

BFS vs DFS: Key Differences

Where Are These Algorithms Used?

BFS Applications:

DFS Applications:

Common Pitfalls to Avoid

• Not resetting the visited array between different calls.
• Stack overflow in DFS (use iterative DFS for large graphs).
• Infinite loops when edges form cycles (without proper visited tracking).

Frequently Asked Questions (FAQs)

Q1: Which is better BFS or DFS?
Depends on the use case. BFS is better for shortest paths, while DFS is great for deep exploration.

Q2: Can we use both BFS and DFS on the same graph?
Yes. You can apply both algorithms to the same graph independently.

Q3: Is recursion required for DFS?
Not required. DFS can be done iteratively using a stack.

Q4: Which is faster?
Their time complexity is the same: O(V + E). Performance depends on the structure of the graph.

Q5: Is BFS/DFS used in real interviews?
Absolutely! They're classic DSA problems for FAANG-level interviews.

Conclusion

Whether you’re solving puzzles, analyzing networks, or optimizing systems BFS and DFS will come up again and again. They’re deceptively simple yet incredibly powerful.

To solidify your understanding, code them from scratch, tweak them, and apply them to real problems.

Want to explore more examples, quizzes, and deep-dive tutorials? Check out Uncodemy’s DSA blog and supercharge your prep!