---
title: "Breadth first traversal in graph"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:bfs-graph-explain"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bfs-graph-explain
site: BCT Engineering
---

# Breadth first traversal in graph

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2072 Asoj, 5 marks; 2070 Magh, 3 marks (asked 2 times)
- Video: [Breadth First Traversal for a Graph | GeeksforGeeks](https://www.youtube.com/watch?v=0u78hx-66Xk) — GeeksforGeeks
- 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-graph-explain
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Explain breadth first traversal in graph with suitable example. (How is the breadth first algorithm implemented?)

## Short answer

Breadth-first traversal visits neighbors level by level using a queue. Start at source, enqueue it, then repeatedly dequeue, enqueue unvisited neighbors. Example: from A, BFS order is A B C D E F. Complexity O(V+E).

## Answer

**Breadth first traversal (BFS)** visits a graph level by level. Starting from a source vertex, it visits the source, then all vertices at distance 1, then distance 2, and so on. A **queue** (FIFO) holds the vertices waiting to be explored, and a *visited* array prevents revisiting.

#### Algorithm
```text
BFS(G, s)
1. mark s visited; enqueue s
2. while queue not empty
3.     v = dequeue(); print v
4.     for each neighbour w of v
5.         if w not visited: mark w visited; enqueue w
```

#### Implementation
Keep three structures: an adjacency matrix or lists for the graph, a visited[] array, and a circular or linear 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
```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.

Start from A:

| 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**

**Complexity:** O(V + E) with adjacency lists, O(V²) with an adjacency matrix. BFS finds shortest paths (fewest edges) in an unweighted graph and is used for connected components and level-order search.

## Check yourself

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

1. What does the queue hold in BFS?
   A. Vertices waiting to be explored
   B. Visited vertices
   C. Edges
   D. Weights
   Answer: A. FIFO order of discovery. (Key point: Queue role)

2. Why is a visited array needed?
   A. To count edges
   B. To prevent revisiting vertices
   C. To sort vertices
   D. To store weights
   Answer: B. Avoids infinite loops on cycles. (Key point: Visited array)

3. In the example, after dequeuing A, what is the queue?
   A. C B
   B. B C D
   C. B C
   D. D E
   Answer: C. A's neighbours B and C are enqueued. (Key point: Step)

4. What does BFS find in an unweighted graph?
   A. Minimum weight paths
   B. Longest paths
   C. Cycles only
   D. Paths with the fewest edges
   Answer: D. Level order gives shortest. (Key point: Shortest path)

## Related in Data Structure and Algorithm

- [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×