# 7.4 BFS & DFS

> Breadth-first search with a queue, depth-first search with recursion or a stack, the visited array, and O(V + E).

Chapter: Graphs · ~60 min · medium
URL: https://dsa.fetehadin.com/learn/bfs-dfs

## Mental model

You drop a stone in a pond. The ripples spread out **ring by ring**: everything 1 step away, then 2 steps, then 3. That is **Breadth-First Search**.

Now you explore a maze. You follow one corridor **as far as it goes**, and only when you hit a dead end do you **back up** to try the last turn you skipped. That is **Depth-First Search**.

### BFS: use a queue

1. Mark the start visited and enqueue it.
2. While the queue is not empty: dequeue u, process it, and enqueue every **unvisited** neighbour (marking it visited **now**).

The queue makes vertices come out in order of distance. So BFS gives the **shortest path in edges**.

### DFS: use a stack (or recursion)

```cpp
void dfs(int u) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u])
        if (!visited[v]) dfs(v);
}
```

The recursion **is** a stack: the call stack remembers where to back up to. An iterative version uses `std::stack`.

### Why "visited"?

Trees have no cycles, so tree traversals never revisit a node. Graphs can have cycles: 0 → 1 → 4 → 3 → 0 → … would loop forever. The **visited** array makes sure every vertex is processed **once**.

### Cost

Each vertex is enqueued (or called) once, and each edge is checked once from each end: **O(V + E)** with an adjacency list. With a matrix, finding a vertex's neighbours scans a whole row, so **O(V²)**.

> Tree level-order traversal (Chapter 6) is just BFS on a tree.

## C++ code: bfs-dfs.cpp

```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

void bfs(int s, const vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;
    visited[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : adj[u])
            if (!visited[v]) {
                visited[v] = true;            // mark when enqueued, not when printed
                q.push(v);
            }
    }
}

void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u])
        if (!visited[v]) dfs(v, adj, visited);
}

void dfsIterative(int s, const vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    stack<int> st;
    st.push(s);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        cout << u << " ";
        for (int i = adj[u].size() - 1; i >= 0; i--)   // push in reverse so the smallest pops first
            if (!visited[adj[u][i]]) st.push(adj[u][i]);
    }
}

int main() {
    vector<vector<int>> adj = {
        {1, 3},        // 0
        {0, 2, 4},     // 1
        {1, 5},        // 2
        {0, 4},        // 3
        {1, 3, 5},     // 4
        {2, 4},        // 5
    };
    cout << "BFS from 0: "; bfs(0, adj); cout << "\n";
    vector<bool> vis(adj.size(), false);
    cout << "DFS from 0: "; dfs(0, adj, vis); cout << "\n";
    cout << "DFS (stack): "; dfsIterative(0, adj); cout << "\n";
}
```

Expected output:

```text
BFS from 0: 0 1 3 2 4 5 
DFS from 0: 0 1 2 5 4 3 
DFS (stack): 0 1 2 5 4 3
```

## Complexity

| Case | Cost |
| --- | --- |
| BFS / DFS with adjacency list | O(V + E) |
| BFS / DFS with adjacency matrix | O(V²) |

Space: O(V) for visited plus the queue or stack

BFS finds the path with the **fewest edges** in an unweighted graph. DFS does not.

## Videos

- [Graph Traversals: BFS & DFS](https://youtu.be/pcKY4hjDrxk) (Abdul Bari): Abdul Bari traces BFS and DFS by hand. The exam format exactly.
- [Binary tree: Level Order Traversal](https://youtu.be/86g8jAQug04) (mycodeschool): Level-order tree traversal, which is BFS on a tree. A good warm-up.

## Exam lens

Likely questions:

- Give the BFS and DFS order of a drawn graph starting from a given vertex.
- Which data structure does BFS use? DFS?
- Write BFS in C++ using an adjacency list.
- Why do we need a visited array in a graph but not in a tree?
- What is the time complexity of BFS/DFS with a list? With a matrix?

Common mistakes:

- No visited array, so the search loops forever around a cycle.
- In BFS, marking a vertex visited when it is **dequeued** instead of **enqueued** (it can be enqueued twice).
- Visiting neighbours in a different order from the one the question uses (usually ascending).
- Forgetting disconnected graphs. Loop over all vertices and start a new search from each unvisited one.

## Quick check

1. Graph on this page, from 0 (neighbours in ascending order). BFS order?
   A. 0 1 2 5 4 3
   B. 0 1 3 2 4 5
   C. 0 3 4 1 2 5
   D. 0 1 2 3 4 5
   Answer: B. Wave 1: 1, 3. Wave 2: 2, 4. Wave 3: 5.

2. Same graph. DFS order?
   A. 0 1 2 5 4 3
   B. 0 1 3 2 4 5
   C. 0 3 4 5 2 1
   D. 0 1 4 3 5 2
   Answer: A. 0 → 1 → 2 → 5 → 4 → 3, going as deep as possible each time.

3. BFS uses a…
   A. stack
   B. queue
   C. heap
   D. hash table
   Answer: B. First discovered, first explored, so FIFO.

4. Shortest path (fewest edges) in an unweighted graph?
   A. DFS
   B. BFS
   C. both always
   D. neither
   Answer: B. BFS reaches all vertices at distance 1 before any at distance 2.

## Practice

**Trace by hand.** Edges A–B, A–C, B–D, C–D, D–E, C–F. Neighbours in alphabetical order. Write the BFS from A (with the queue after each dequeue) and the DFS from A.

Solution:

BFS: dequeue A → queue B C · B → C D · C → D F · D → F E · F → E · E → empty.
**BFS: A B C D F E**

DFS: A → B → D → C → F (back) → E. **DFS: A B D C F E**


**Implement it.** Use BFS to compute the distance (number of edges) from a source to every vertex, and count connected components with DFS.

Hint: Distance: `dist[v] = dist[u] + 1` when v is first enqueued. Components: loop over all vertices, and each time you find an unvisited one, run DFS and add 1.

**Problems:**

- [Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/) (easy). Hint: BFS or DFS from source; check whether destination is visited.
- [Flood Fill](https://leetcode.com/problems/flood-fill/) (easy). Hint: The grid is a graph where each cell has up to 4 neighbours. DFS from the start cell.
- [Number of Islands](https://leetcode.com/problems/number-of-islands/) (medium). Hint: Count how many times you must start a new DFS. That is connected components on a grid.

## Mastery checklist

- [ ] I can trace BFS and DFS by hand on a graph.
- [ ] I can write BFS with a queue and DFS with recursion.
- [ ] I can explain why graphs need a visited array.
- [ ] I know both are O(V + E) with an adjacency list.