---
title: "BFS and DFS with example"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:bfs-dfs-explain-example"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bfs-dfs-explain-example
site: BCT Engineering
---

# BFS and DFS with example

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2069 Bhadra, 5 marks; 2073 Bhadra, 3 marks (asked 2 times)
- Video: [L-4.15: BFS & DFS | Breadth First Search | Depth First Search | Graph Traversing | DAA](https://www.youtube.com/watch?v=N2P7w22tN9c) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bfs-dfs-explain-example
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Explain depth first traversal and breadth first traversal in graph with suitable example.

## Short answer

DFS uses a stack to go deep; BFS uses a queue to visit level by level. In the example graph with A connected to B and C, B to D and E, C to F, and E-F, DFS from A gives A B D E F C, while BFS gives A B C D E F. Both have O(V+E) time.

## Answer

#### Depth first traversal (DFS)
Goes as deep as possible along each path, then backtracks. Uses a **stack** (or recursion). From a vertex, move to an unvisited neighbour; when none remains, pop back.
```c
int adj[N][N], visited[N], n;
void dfs(int v) {
    visited[v] = 1;
    printf("%d ", v);
    for (int w = 0; w < n; w++)
        if (adj[v][w] && !visited[w])
            dfs(w);
}
```

#### Breadth first traversal (BFS)
Visits the start vertex, then all its neighbours, then their neighbours, level by level. Uses a **queue**.
```c
int adj[N][N], visited[N], n;
void bfs(int s) {
    int queue[N], front = 0, rear = 0;
    visited[s] = 1; queue[rear++] = s;
    while (front < rear) {
        int v = queue[front++];            /* dequeue */
        printf("%d ", v);
        for (int w = 0; w < n; w++)
            if (adj[v][w] && !visited[w]) {
                visited[w] = 1;
                queue[rear++] = w;         /* enqueue */
            }
    }
}
```

#### Example graph
```text
        A
       / \
      B   C
     / \   \
    D   E---F
```
Edges: A-B, A-C, B-D, B-E, C-F, E-F. Adjacency lists (alphabetical): A: B, C; B: A, D, E; C: A, F; D: B; E: B, F; F: C, E.

**BFS from A** (queue):

| Step | Dequeued | Newly enqueued | Queue after step | Output |
|---|---|---|---|---|
| 0 | - | A | A | |
| 1 | A | B, C | B C | A |
| 2 | B | D, E | C D E | A B |
| 3 | C | F | D E F | A B C |
| 4 | D | none | E F | A B C D |
| 5 | E | none (F already queued) | F | A B C D E |
| 6 | F | none | empty | A B C D E F |

**BFS order: A B C D E F**

**DFS from A** (stack, alphabetical order): A → B → D (dead end, back to B) → E → F → C.

**DFS order: A B D E F C**

Both take O(V + E) time with adjacency lists.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does BFS use?
   A. A stack
   B. Recursion only
   C. A queue
   D. A heap
   Answer: C. FIFO gives level order. (Key point: BFS structure)

2. BFS order from A in the example?
   A. A B D E F C
   B. A C B F E D
   C. A B D C E F
   D. A B C D E F
   Answer: D. Level by level. (Key point: BFS order)

3. DFS order from A?
   A. A B D E F C
   B. A B C D E F
   C. A B D C F E
   D. A C F E B D
   Answer: A. Deep first. (Key point: DFS order)

4. Time for both with adjacency lists?
   A. O(V^2)
   B. O(V + E)
   C. O(E log V)
   D. O(V log E)
   Answer: B. Same. (Key point: Complexity)

## Close variants set in other exams

- [Depth first traversal in graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adfs-graph-explain) — Data Structure and Algorithm, chapter 10, asked 4×

## Related in Data Structure and Algorithm

- [Breadth first traversal in graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abfs-graph-explain) — Data Structure and Algorithm, chapter 10, asked 2×
- [Differences between DFS and BFS](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adfs-vs-bfs-differences) — Data Structure and Algorithm, chapter 10

## Related in other subjects

- [Searching: BFS vs DFS comparison](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ablind-search-dfs-bfs-compare) — Artificial Intelligence, chapter 3, asked 5×
- [Informed vs blind search; DFS vs BFS](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ainformed-vs-blind-search-dfs-bfs) — Artificial Intelligence, chapter 3
- [Rectangular beam dimensions, depth twice breadth](https://www.bctengineer.com/question.md?key=semester_3%2Fstrength_of_materials%3Arect-beam-udl-point-load-depth) — Strength of Materials, chapter 7