Neural Sync Active

Week 9: Graph Traversal — BFS & DFS

Registry Synced

Week 9: Graph Traversal — BFS & DFS

3847 words

19 min read

2026-09-12

Reading compass

Now · TL;DR

Computational Thinking — Week 9: Graph Traversal — BFS & DFS

IITM’s CT Week 9 moves from representing graphs to systematically exploring them, with Breadth-First Search and Depth-First Search.

TL;DR

A graph may contain many vertices and edges, but simply storing it is not enough. We often need to answer:

Which vertices can I reach?
In what order should I explore them?
Is there a path from $A$ to $B$ ?
How far is a vertex in terms of number of edges?
Have I already processed this vertex?

Two fundamental traversal algorithms solve these problems:

BFS — Breadth-First Search

Explore level by level:


text
start
↓
all immediate neighbors
↓
neighbors of those neighbors
↓
...

Uses a:

\boxed{\text{queue}}

DFS — Depth-First Search

Explore as far as possible along one branch, then backtrack:


text
start
↓
go deep
↓
go deeper
↓
dead end
↓
backtrack

Uses conceptually:

\boxed{\text{stack / recursion}}

1. Why graph traversal is needed

Suppose we have:


text
A --- B --- D
|     |
C --- E

Knowing the graph exists does not automatically answer:

Which vertices are reachable from A?

An algorithm must systematically inspect the graph.

That is graph traversal.

2. Traversal

Traversal means:

visit vertices according to a systematic rule.

A traversal algorithm generally needs to:

choose a starting vertex
visit it
inspect connected vertices
remember what has already been visited
continue until no relevant unvisited vertices remain

3. Why `visited` is necessary

Consider a cycle:


text
A --- B
|     |
D --- C

If the algorithm simply follows neighbors without remembering previous vertices, it could do:


text
A → B → C → D → A → B → C → ...

forever.

So we maintain something like:


text
visited

to avoid processing the same vertex repeatedly.

4. Generic traversal idea

Conceptually:


text
mark start as discovered

while there is something left to explore:
    choose next vertex
    examine its neighbors

    for each neighbor:
        if neighbor has not been visited:
            mark/discover it
            schedule it for later exploration

The major difference between BFS and DFS is:

How do we choose the next vertex?

5. Breadth-First Search

BFS explores a graph breadth first.

Starting from vertex

s

visit $s$
visit all vertices one edge away
then all vertices two edges away
then three edges away
and so on

6. BFS level intuition

Example:


text
        A
      /   \
     B     C
    / \     \
   D   E     F

Starting at:

A

BFS conceptually explores:

Level 0

A

Level 1

B,C

Level 2

D,E,F

So one possible BFS order is:

\boxed{ A,B,C,D,E,F }

assuming neighbors are considered left-to-right/alphabetically as shown.

7. BFS uses a queue

A queue follows:

\boxed{\text{FIFO}}

meaning:

First In, First Out.

Like a line of people:


text
front → A, B, C ← rear

The item inserted earliest is removed first.

8. Why FIFO gives breadth-first behavior

Suppose we start at A.

Queue:


text
[A]

Remove A and discover B and C:


text
[B, C]

B entered first, so B is processed before C.

When processing B, suppose D and E are discovered:


text
[C, D, E]

Notice C, which is still at the same level as B, gets processed before deeper vertices D and E.

That is exactly why BFS proceeds level by level.

9. BFS conceptual pseudocode

A standard form is:


text
mark start as visited
enqueue start

while queue is not empty:
    v = dequeue

    for each neighbor u of v:
        if u is not visited:
            mark u as visited
            enqueue u

The exact IITM notation may differ, but this is the core algorithmic structure.

10. BFS trace

Graph:


text
A --- B --- D
|     |
C --- E

Assume neighbors are considered alphabetically.

Start at:

A.

Initial state


text
Queue   = [A]
Visited = {A}

Process A.

Neighbors:

B,C.

Now:


text
Queue   = [B, C]
Visited = {A, B, C}

11. Continue BFS

Process B.

Neighbors may include:

A,D,E.

A already visited.

Discover D and E:


text
Queue   = [C, D, E]
Visited = {A, B, C, D, E}

Process C.

Its relevant neighbor E is already discovered.


text
Queue = [D, E]

Then process D and E.

Traversal order:

\boxed{ A,B,C,D,E }

12. Mark when discovered, not too late

A subtle but important pattern:

When an unvisited neighbor is first discovered, mark it immediately.

Conceptually:


text
if u not visited:
    visited[u] = True
    enqueue(u)

Why?

Suppose two current vertices both point to the same unvisited vertex.

If you wait until dequeue time to mark it, the same vertex might be inserted multiple times.

13. BFS finds shortest paths in unweighted graphs

One of BFS's most important properties:

In an unweighted graph, BFS discovers vertices in increasing number of edges from the source.

Therefore BFS can find shortest path distance measured in number of edges.

14. BFS distances

Suppose:


text
        A
      /   \
     B     C
     |     |
     D --- E

Starting from A:

d(A)=0

d(B)=d(C)=1

d(D)=d(E)=2

assuming those are the shortest available routes.

15. Why BFS shortest path works

BFS processes:

\text{distance }0

before:

\text{distance }1

before:

\text{distance }2

and so on.

Therefore the first time a vertex is discovered, BFS has found a minimum-edge route to it.

16. Parent / predecessor

To reconstruct a BFS path, store how each vertex was first reached.

Example:


text
parent[B] = A
parent[C] = A
parent[D] = B

Then if you want the path from A to D:


text
D
↑
B
↑
A

reverse it:

\boxed{ A\to B\to D }

17. BFS and weighted graphs

Be careful:

BFS finds shortest paths by edge count.

If edges have different costs:


text
A --100-- B
A --1-- C --1-- B

BFS may regard direct A→B as one hop.

But weighted cost:

100

is worse than:

1+1=2.

So ordinary BFS is not a general weighted shortest-path algorithm.

18. Depth-First Search

DFS explores one branch as deeply as possible before returning.

Example:


text
        A
      /   \
     B     C
    / \
   D   E

One DFS starting at A might visit:

A\to B\to D

then backtrack to B, visit E, then backtrack and eventually visit C.

Possible order:

\boxed{ A,B,D,E,C }

19. DFS mental model

Think:

keep moving forward while an unvisited neighbor exists.

If you reach a vertex with no unvisited neighbors:

go backward to the most recent unfinished vertex.

This backward movement is backtracking.

20. DFS uses a stack conceptually

A stack follows:

\boxed{\text{LIFO}}

meaning:

Last In, First Out.

Example:


text
bottom [A, B, C] top

C was added last, so C is removed first.

This naturally creates deep exploration.

21. Recursion and DFS

DFS can also be expressed recursively:


text
DFS(v):
    mark v visited

    for each neighbor u of v:
        if u not visited:
            DFS(u)

The call stack implicitly remembers where to return after exploring a branch.

22. Recursive DFS intuition

Suppose:


text
A → B → D
    |
    E

Call:


text
DFS(A)

which calls:


text
DFS(B)

which calls:


text
DFS(D)

When D has nowhere new to go, return to B.

Then B can continue with E.

This is backtracking via recursive calls.

23. Iterative DFS

DFS can also use an explicit stack:


text
push start

while stack is not empty:
    v = pop

    if v not visited:
        mark v visited

        push appropriate neighbors

The exact traversal order depends on the order in which neighbors are pushed.

24. DFS trace example

Graph:


text
A --- B --- D
|     |
C --- E

Assume alphabetic preference where possible.

Starting at A:

A

Choose B:

A\to B

From B choose D:

A\to B\to D.

D has no new neighbor.

Backtrack to B.

Then choose E:

A\to B\to E.

From E, C may be discovered.

Possible DFS order:

\boxed{ A,B,D,E,C }

25. BFS vs DFS order is not always unique

The graph alone may not determine a unique traversal order.

Suppose A has neighbors:

B,C,D.

If no neighbor-order rule is specified, BFS might process them in several valid orders.

Likewise DFS can choose different branches first.

Therefore:

\boxed{ \text{Traversal order depends on neighbor ordering} }

unless the question specifies an ordering convention.

26. BFS vs DFS comparison

Feature	BFS	DFS
Exploration	Level by level	Deep branch first
Main structure	Queue	Stack / recursion
Principle	FIFO	LIFO
Unweighted shortest paths	Yes	Not generally
Backtracking	Not central	Central
Reachability	Yes	Yes

27. Both can determine reachability

Suppose the question is simply:

Is C reachable from A?

Either BFS or DFS can search from A.

If C is eventually visited:

\boxed{\text{reachable}}

If traversal finishes without C:

\boxed{\text{not reachable}}

28. Connected components using traversal

For an undirected graph:

choose an unvisited vertex
BFS/DFS from it
all reached vertices form one connected component
choose another unvisited vertex
repeat

So graph traversal can identify connected components.

29. Example

Graph:


text
A --- B --- C

D --- E

F

Run DFS/BFS from A:

\{A,B,C\}

Run from next unvisited D:

\{D,E\}

Then F:

\{F\}.

Thus:

\boxed{3\text{ connected components}}

30. Traversal using adjacency matrix

Suppose:

M= \begin{bmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{bmatrix}.

To find neighbors of vertex

i

, scan row

i

For every:

M_{ij}=1,

vertex

j

is adjacent.

So BFS/DFS can operate directly on the Week 8 adjacency-matrix representation.

31. Cost of matrix neighbor search

If there are:

n

vertices, scanning one adjacency-matrix row checks:

n

possible neighbors.

Doing this for many vertices may inspect roughly:

n^2

matrix entries.

This follows directly from the matrix representation.

32. Traversal with adjacency lists

Another representation could store only actual neighbors:


text
A: [B,C]
B: [A,D]
C: [A]
D: [B]

Then traversal only iterates through listed edges.

This is often useful for sparse graphs.

The Week 9 core idea, however, is traversal logic rather than one mandatory storage representation.

33. Visited structure

visited can conceptually be:

Boolean array
dictionary
set
status column

Example:


text
visited[A] = True
visited[B] = False

The implementation varies, but the purpose is the same.

34. Vertex states

A useful conceptual refinement is:

Undiscovered

Never encountered.

Discovered

Found and scheduled for processing.

Processed

Its neighbors have been examined.

BFS especially benefits from distinguishing discovery from final processing.

35. Example BFS state table

Graph:


text
A --- B
|     |
C --- D

Start A.

Step	Removed	Queue after	Newly discovered
Start	—	`[A]`	A
1	A	`[B,C]`	B,C
2	B	`[C,D]`	D
3	C	`[D]`	—
4	D	`[]`	—

One BFS order:

A,B,C,D.

36. Example DFS stack intuition

Same graph:


text
A --- B
|     |
C --- D

A possible DFS:


text
A
↓
B
↓
D
↓
C

Then all vertices are visited.

Different neighbor ordering could instead produce:

A,C,D,B.

Both may be valid.

37. Cycles and `visited`

Consider:


text
A --- B
 \   /
   C

DFS:

A\to B\to C.

At C, A is already visited.

So do not recurse into A again.

This prevents infinite cycling.

BFS uses the same principle.

38. DFS tree

During DFS, the edges used to first discover vertices form a traversal tree.

Example:


text
A
|
B
|
D

and perhaps another branch:


text
B
|
E

These discovery relationships can be represented using parent pointers.

39. BFS tree

Similarly, first-discovery edges in BFS form a BFS tree rooted at the source.

For unweighted graphs, tree depth corresponds to shortest-path distance from the source.

That is why BFS levels matter.

40. BFS level formula intuition

If vertex

u

is discovered from

v

, then:

d(u)=d(v)+1

when

u

is first reached by BFS.

Start:

d(s)=0.

This lets BFS compute minimum hop counts.

41. Search can stop early

If the goal is only:

Find whether target T is reachable.

Then when T is discovered/found, the search may stop depending on the exact algorithm.

You do not always need to traverse the whole component.

42. Traversal of disconnected graph

A BFS or DFS from one source only explores vertices reachable from that source.

Example:


text
A --- B    C --- D

BFS from A visits:

A,B.

It will never automatically reach:

C,D.

To traverse the entire graph, start new searches from remaining unvisited vertices.

Common mistake: BFS uses stack

Wrong.

Standard association:

\boxed{ \text{BFS}\rightarrow\text{Queue} }

\boxed{ \text{DFS}\rightarrow\text{Stack / recursion} }

This distinction is fundamental.

Common mistake: DFS finds unweighted shortest path

DFS may find a path, but not necessarily a shortest one.

Example:


text
A --- B
|     |
C --- D --- E
 \--------- E

Depending on exploration order, DFS may take a long route before finding E even though a shorter route exists.

BFS is the standard choice for minimum number of edges.

Common mistake: mark visited only after everything finishes

If marking is delayed too much, the same vertex can be scheduled repeatedly.

For BFS especially, mark when the vertex is first discovered/enqueued.

Common mistake: visit same vertex repeatedly

In a graph with cycles, this may cause:

duplicated work
duplicated outputs
nontermination

Always track visited state unless the particular algorithm intentionally allows revisits.

Common mistake: BFS order assumed unique

If adjacency order is unspecified, several BFS orders can be valid.

What remains invariant is the level structure.

Vertices at smaller distance from the source are discovered before vertices at greater distance.

Common mistake: DFS means "always go left"

No.

"Left" only exists in a particular drawing.

DFS means:

choose an unvisited neighbor and continue deeply.

Which neighbor is chosen depends on the ordering convention.

Common mistake: graph drawing determines algorithm

Two drawings can represent the same graph.

Traversal depends on:

vertices
edges
neighbor ordering

not on arbitrary visual placement on the page.

Common mistake: directed reachability treated as undirected

Graph:


text
A ---> B ---> C

From A:

C

is reachable.

From C:

A

is not reachable unless reverse paths exist.

Follow arrow directions.

Common mistake: queue and stack behavior reversed

Queue


text
enqueue A
enqueue B
remove → A

FIFO.

Stack


text
push A
push B
remove → B

LIFO.

This difference produces BFS vs DFS behavior.

52. Queue trace mini-example

Start empty:


text
[]

enqueue A:


text
[A]

enqueue B:


text
[A,B]

dequeue:


text
A

remaining:


text
[B]

53. Stack trace mini-example

Start:


text
[]

push A:


text
[A]

push B:


text
[A,B]

pop:


text
B

remaining:


text
[A]

54. BFS worked example

Graph:


text
        A
      /   \
     B     C
    / \   /
   D   E F

Assume alphabetical neighbor ordering.

Start:


text
Q = [A]
Visited = {A}

Process A:


text
Q = [B,C]

Process B:


text
Q = [C,D,E]

Process C:


text
Q = [D,E,F]

Then D, E, F.

BFS:

\boxed{ A,B,C,D,E,F }

55. DFS on the same graph

Starting at A, alphabetical choice:

A\to B.

From B:

B\to D.

D ends → backtrack to B.

Then:

B\to E.

Backtrack to A.

Then:

A\to C\to F.

DFS order:

\boxed{ A,B,D,E,C,F }

Same graph, different traversal.

56. BFS vs DFS visual intuition


text
BFS:
         A
      ↙     ↘
     B       C
   ↙  ↘    ↙  ↘
  D    E   F    G

Process horizontally by layers.


text
DFS:
A
↓
B
↓
D
↓
...
backtrack
↓
next branch

57. When BFS is naturally useful

BFS fits problems involving:

minimum number of connections
shortest path in unweighted graph
degrees of separation
nearest reachable target
level-by-level exploration

Example:

What is the minimum number of flights needed if every flight counts equally?

58. When DFS is naturally useful

DFS fits problems involving:

exhaustive exploration
connected components
cycle-oriented reasoning
backtracking
exploring one branch deeply

The exact applications grow in later algorithms, but the traversal pattern itself is foundational.

59. BFS/DFS are algorithmic patterns

Do not memorize them merely as graph-specific recipes.

They represent broader scheduling philosophies:

BFS

Explore possibilities in increasing "distance/depth."

DFS

Commit deeply to one possibility, then backtrack.

These patterns appear elsewhere in computer science and AI search.

60. Relationship to Week 3 procedures

DFS's recursive form is a direct application of procedures calling themselves:


text
DFS(v):
    ...
    DFS(u)

That is recursion.

Even if recursion is not the main Week 9 syllabus label, the connection explains why procedures matter for graph algorithms.

61. Relationship to Week 4 nested iteration

When traversing via adjacency matrix:


text
for each visited vertex i:
    inspect columns j

the algorithm repeatedly scans matrix rows.

So graph traversal combines:

loops
conditions
data structures
state
matrix representation

Everything from earlier CT weeks starts coming together.

62. Relationship to Week 6 dictionaries

You can conceptually store:


text
visited[vertex]
distance[vertex]
parent[vertex]

as dictionary-like mappings.

Example:


text
distance[A] = 0
distance[B] = 1

Graph algorithms depend heavily on such per-vertex state.

63. Relationship to Week 8 adjacency matrices

Week 8 answered:

Which vertices are neighbors?

Week 9 answers:

In what order should we repeatedly follow those neighbor relationships?

Thus:

\boxed{ \text{representation} \rightarrow \text{traversal algorithm} }

64. Exam-solving workflow

When asked to trace BFS or DFS:

Write the starting vertex.
Write the specified neighbor ordering.
Maintain visited.
For BFS, maintain the queue after every step.
For DFS, maintain the recursion/stack path or backtracking state.
Never revisit an already discovered vertex unless pseudocode explicitly says otherwise.
Record the traversal order.
If asked for distances/parents, maintain those separately.

65. BFS trace template

Use:

Step	Vertex processed	Queue	Newly visited
0	—	`[start]`	start
1	...	...	...
2	...	...	...

This prevents queue-order mistakes.

66. DFS trace template

Use:

Step	Current vertex	Action	Active path/stack
1	A	visit	A
2	B	go deeper	A→B
3	D	go deeper	A→B→D
4	D	dead end/backtrack	A→B

This makes backtracking explicit.

67. Compact formula / fact sheet

BFS

\boxed{\text{Queue}}

\boxed{\text{FIFO}}

\boxed{\text{level-by-level}}

For an unweighted graph:

\boxed{ \text{first discovery distance} = \text{shortest number of edges} }

DFS

\boxed{\text{Stack / recursion}}

\boxed{\text{LIFO}}

\boxed{\text{deep-first + backtracking}}

Both require:

\boxed{\text{visited tracking}}

68. Week 9 conceptual map


text
GRAPH REPRESENTATION
        ↓
Choose start vertex
        ↓
Track visited vertices
        ↓
      TRAVERSAL
      /       \
    BFS       DFS
     |         |
   Queue    Stack/
   FIFO     Recursion
     |         |
  Levels     Depth
     |         |
Shortest    Backtrack
unweighted
distance

69. What you should actually master

By the end of CT Week 9, you should be able to:

Explain what graph traversal means.
Explain why a visited structure is necessary.
Describe BFS conceptually.
Trace a BFS queue.
Understand FIFO.
Recognize BFS's level-by-level behavior.
Compute unweighted shortest-path distance using BFS logic.
Understand parent/predecessor information.
Describe DFS conceptually.
Trace DFS and backtracking.
Understand LIFO.
Relate DFS to stacks/recursion.
Distinguish BFS from DFS.
Recognize that traversal order can depend on neighbor ordering.
Use either traversal for reachability.
Understand how traversal finds connected components.
Correctly follow edge direction in directed graphs.
Apply BFS/DFS to adjacency-matrix or neighbor-list representations.

If those are comfortable, Computational Thinking Week 9 is under control.

Quick Recall & Flashcards

Test your active recall before proceeding to practice problems. Format:

Question :: Answer.

Week 9 Diagnostic: Which data structure does Breadth-First Search (BFS) use to manage the discovery frontier? :: Answer: B — BFS processes nodes in level order using a First-In, First-Out Queue.
Week 9 Diagnostic: Why is a visited set or boolean array necessary during graph traversal? :: Answer: B — In graphs with cycles, failing to track visited vertices causes the traversal algorithm to loop infinitely.

Practice & Self-Check

Attempt these diagnostic questions to verify your operational understanding.

Question 1

Which data structure does Breadth-First Search (BFS) use to manage the discovery frontier?

MCQ

3 Unit Assessment

A. Stack (LIFO)

B. Queue (FIFO)

C. Binary Search Tree

D. Priority Queue

Question 2

Why is a visited set or boolean array necessary during graph traversal?

MCQ

3 Unit Assessment

A. To count the total number of edges

B. To prevent revisiting vertices and getting trapped in infinite loops in cyclic graphs

C. To sort the vertices alphabetically

D. To calculate edge weights