BFS and DFS — Exploring Graphs Step by Step

Real-world analogy

What is it?

BFS (Breadth-First Search) and DFS (Depth-First Search) are the two fundamental ways to explore every node in a graph. BFS uses a queue and explores level by level, making it ideal for shortest paths in unweighted graphs. DFS uses recursion or a stack and explores as deep as possible, making it great for finding connected components and exploring all paths.

Real-world relevance

GPS navigation apps use BFS to find the shortest route between two locations on a road map. Social media platforms use BFS to suggest 'People You May Know' by exploring friends-of-friends. DFS is used in puzzle solvers (like solving a Sudoku by trying each possibility deeply), in web crawlers that follow links as deep as they go, and in detecting cycles in dependency graphs (like making sure software packages do not depend on each other in a loop).

Key points

• BFS — Breadth-First Search — BFS explores a graph level by level, like ripples in water. Start at a node, visit all its direct neighbors first, then visit all THEIR neighbors, and so on. It uses a queue (FIFO) to remember which nodes to visit next. BFS always visits closer nodes before farther ones, which makes it perfect for finding shortest paths!
• How BFS Works Step by Step — Step 1: Put the starting node in a queue and mark it visited. Step 2: Take the front node from the queue. Step 3: Look at all its unvisited neighbors, mark them visited, and add them to the queue. Step 4: Repeat until the queue is empty. Because the queue is first-in-first-out, nodes discovered first are processed first — guaranteeing level-order exploration!
• BFS Finds Shortest Paths — In an unweighted graph (where every edge has the same cost), BFS guarantees the shortest path from the start to every other node. Why? Because it visits all nodes at distance 1 before distance 2, all at distance 2 before distance 3, and so on. The first time BFS reaches a node, that is the shortest way to get there. This is super useful in contests!
• DFS — Depth-First Search — DFS explores a graph by going as deep as possible before backtracking. Start at a node, pick one neighbor, go to it, pick one of ITS neighbors, keep going deeper until you hit a dead end (no unvisited neighbors). Then backtrack and try another path. It uses either recursion or a stack (LIFO). DFS is like an adventurer who always picks the deepest unexplored tunnel!
• How DFS Works Step by Step — Step 1: Start at a node and mark it visited. Step 2: Pick any unvisited neighbor and recursively DFS into it. Step 3: When you reach a node with no unvisited neighbors, backtrack to the previous node. Step 4: Try other unvisited neighbors from there. Step 5: Keep going until all reachable nodes are visited. The recursion naturally handles the backtracking for you!
• Connected Components with DFS — A connected component is a group of nodes where you can travel between any two using some path. To count components, loop through all nodes. When you find an unvisited node, start a DFS from it — this marks all nodes in that component. Each time you need to start a new DFS, that means you found a new component. If the whole graph has one component, it is called connected!
• When to Use BFS vs DFS — Use BFS when you need the shortest path in an unweighted graph, or when you need to explore level by level. Use DFS when you need to explore all paths, find connected components, detect cycles, or check if a graph is bipartite. Both have the same time complexity O(V + E), but they solve different types of problems. A good competitive programmer knows when to pick each one!
• BFS on a Grid — Flood Fill — Many contest problems give you a 2D grid instead of a graph. You can still use BFS and DFS! Each cell is a node, and neighboring cells (up, down, left, right) are edges. BFS on a grid finds the shortest path from one cell to another. This technique is called flood fill and it appears in tons of contest problems — like counting islands or finding the nearest exit in a maze!
• Common Mistakes to Avoid — The biggest mistake is forgetting to mark nodes as visited! Without this, BFS or DFS will loop forever on graphs with cycles. Another mistake is using BFS for weighted graphs — BFS only finds shortest paths when all edges have equal weight. For weighted graphs, you need Dijkstra's algorithm. Always double-check your visited array and make sure you mark nodes BEFORE or WHEN you push them, not after!

Code example

#include <bits/stdc++.h>
using namespace std;

// BFS — find shortest distances from a starting node
void bfs(int start, vector<vector<int>>& adj, int n) {
    vector<int> dist(n + 1, -1);   // -1 means not visited yet
    queue<int> q;

    dist[start] = 0;               // Start node is 0 steps away
    q.push(start);                 // Add start to the queue

    while (!q.empty()) {
        int node = q.front();      // Grab the next node to process
        q.pop();

        for (int nb : adj[node]) { // Look at each neighbor
            if (dist[nb] == -1) {  // If we have not visited it
                dist[nb] = dist[node] + 1;  // It is one step farther
                q.push(nb);        // Add it to the queue
            }
        }
    }

    // Show shortest distances from start to every node
    for (int i = 1; i <= n; i++) {
        cout << "Distance to " << i << ": " << dist[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Graph with 7 nodes, two groups: {1,2,3,4} and {5,6,7}
    int n = 7;
    vector<vector<int>> adj(n + 1);  // Adjacency list (1-indexed)

    // Group 1 edges: 1-2, 2-3, 3-4, 1-4
    adj[1].push_back(2); adj[2].push_back(1);
    adj[2].push_back(3); adj[3].push_back(2);
    adj[3].push_back(4); adj[4].push_back(3);
    adj[1].push_back(4); adj[4].push_back(1);

    // Group 2 edges: 5-6, 6-7
    adj[5].push_back(6); adj[6].push_back(5);
    adj[6].push_back(7); adj[7].push_back(6);

    cout << "=== BFS Shortest Paths from Node 1 ===\n";
    bfs(1, adj, n);
    // Nodes 5, 6, 7 are not connected to node 1, so distance = -1

    return 0;
}

Line-by-line walkthrough

1. 1. We include bits/stdc++.h for all standard library features. Our graph is stored as vector> adj — an adjacency list where adj[i] contains all neighbors of node i.
2. 2. In bfs(), we create a dist[] array initialized to -1 (meaning unvisited). We set dist[start] = 0 and push the start node into a queue. The queue ensures we process nodes in the order they were discovered.
3. 3. The BFS while loop takes the front node from the queue, then checks each neighbor. The critical check 'if (dist[neighbor] == -1)' ensures we only visit each node once. Without this, cycles would cause infinite loops!
4. 4. When we find an unvisited neighbor, we set dist[neighbor] = dist[node] + 1. This works because BFS explores level by level — every neighbor is exactly one step farther than the current node.
5. 5. In countComponents(), we loop through all nodes 1 to n. Each time we find an unvisited node, we increment the component counter and run DFS from that node to mark all reachable nodes as visited.
6. 6. The DFS uses a stack instead of recursion to avoid stack overflow on large graphs. We push the start, then repeatedly pop a node, check its neighbors, and push any unvisited ones onto the stack.
7. 7. In main(), we build a graph with 7 nodes forming two components: {1,2,3,4} connected in a square, and {5,6,7} connected in a line. This lets us test both BFS distances and component counting.
8. 8. BFS from node 1 will find distances 0, 1, 2, 1, -1, -1, -1 for nodes 1 through 7. Nodes 5, 6, 7 are unreachable from node 1, so their distance stays -1.
9. 9. The component counter will find exactly 2 components. First DFS starts at node 1 and marks {1,2,3,4}. Then the loop reaches node 5 (unvisited), starts a second DFS marking {5,6,7}.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

void bfs(int start, vector<vector<int>>& adj, int n) {
    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

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

        for (int neighbor : adj[node]) {
            dist[neighbor] = dist[node] + 1;
            q.push(neighbor);
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << "Distance to " << i << ": " << dist[i] << "\n";
    }
}

int main() {
    int n = 3;
    vector<vector<int>> adj(n + 1);
    adj[1].push_back(2); adj[2].push_back(1);
    adj[2].push_back(3); adj[3].push_back(2);
    adj[1].push_back(3); adj[3].push_back(1);

    bfs(1, adj, n);
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• BFS and DFS Explained Visually (YouTube — Reducible)
• Graph Traversal — BFS and DFS (USACO Guide)
• BFS and DFS Practice Problems (CSES)