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

# Depth first traversal in graph

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2074 Bhadra, 4 marks; 2070 Bhadra, 5 marks (asked 2 times)
- Video: [Depth First Traversal for a Graph | GeeksforGeeks](https://www.youtube.com/watch?v=Y40bRyPQQr0) — 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/dfs-graph-explain
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Explain Depth first traversal in graph with example.

## Short answer

Depth-first traversal explores as far as possible along a branch before backtracking, using a stack or recursion. For example, starting at A in graph A-B, A-C, B-D, B-E, C-F, E-F, DFS order is A B D E F C. Complexity O(V+E).

## Answer

**Depth first traversal (DFS)** visits the vertices of a graph by going as deep as possible along a path before backtracking. It starts from a source vertex, marks it visited, then moves to an unvisited neighbour, and continues until a vertex has no unvisited neighbour; then it backtracks to the previous vertex and tries the next neighbour. It uses a **stack** (or recursion).

#### Algorithm (using a stack)
```text
DFS(G, start)
1. push start on stack, mark start visited, print it
2. while stack not empty
3.     v = top of stack
4.     if v has an unvisited neighbour w
5.         mark w visited, print w, push w
6.     else  pop stack          // backtrack
```
Recursive version:
```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);
}
```

#### 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 at A, choosing neighbours in alphabetical order:

| Step | Current | Action | Stack (bottom to top) | Visited order |
|---|---|---|---|---|
| 1 | A | visit A | A | A |
| 2 | B | visit B | A B | A B |
| 3 | D | visit D | A B D | A B D |
| 4 | D | no new neighbour, pop | A B | A B D |
| 5 | E | visit E | A B E | A B D E |
| 6 | F | visit F | A B E F | A B D E F |
| 7 | C | visit C (from F) | A B E F C | A B D E F C |
| 8 | - | all visited, pop until empty | | |

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

**Complexity:** O(V + E) with adjacency lists, O(V²) with an adjacency matrix. Uses: cycle detection, topological sort, connected components, path finding.

## Check yourself

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

1. Which structure does DFS use?
   A. Stack (or recursion)
   B. Queue
   C. Heap
   D. Hash table
   Answer: A. Backtracking is stack-like. (Key point: DFS data structure)

2. When does DFS backtrack?
   A. After each visit
   B. When the current vertex has no unvisited neighbour
   C. When the graph ends
   D. When it finds a cycle
   Answer: B. It pops back to the previous vertex. (Key point: Backtracking)

3. What is the DFS order from A in the example (alphabetical)?
   A. A B C D E F
   B. A C F E B D
   C. A B D E F C
   D. A B D C F E
   Answer: C. B, then D (dead end), E, F, then C. (Key point: DFS order)

4. DFS time with adjacency lists?
   A. O(V^2)
   B. O(E^2)
   C. O(log V)
   D. O(V + E)
   Answer: D. Each vertex and edge once. (Key point: Complexity)

## Close variants set in other exams

- [BFS and DFS with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abfs-dfs-explain-example) — 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×