BFS Breadth First Search on Graph in DSA C - Execution Trace

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Mark node visited

↓

Add node to queue

↓

While queue not empty

↓

Dequeue node

↓

Visit all unvisited neighbors

↓

Mark neighbors visited and enqueue

↓

Repeat loop

BFS starts at a node, visits neighbors level by level using a queue, marking nodes visited to avoid repeats.

Execution Sample

DSA C

graph = {
  'A': ['B', 'D'],
  'B': ['A', 'C'],
  'C': ['B', 'F'],
  'D': ['A', 'E'],
  'E': ['D', 'F'],
  'F': ['C', 'E']
}

def bfs(start):
    visited = set()
    queue = []
    visited.add(start)
    queue.append(start)

    while queue:
        node = queue.pop(0)
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

bfs('A')

Perform BFS starting from node 'A' on the given graph.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Visual State
1	Start BFS	A	[A]	{A}	A (visited)
2	Dequeue node	A	[]	{A}	A (visited)
3	Visit neighbors B, D	A	[B, D]	{A, B, D}	A (visited) -> B (visited), D (visited)
4	Dequeue node	B	[D]	{A, B, D}	A -> B, D
5	Visit neighbors C (A already visited)	B	[D, C]	{A, B, C, D}	A -> B -> C, D
6	Dequeue node	D	[C]	{A, B, C, D}	A -> B -> C, D
7	Visit neighbors E (A visited)	D	[C, E]	{A, B, C, D, E}	A -> B -> C, D -> E
8	Dequeue node	C	[E]	{A, B, C, D, E}	A -> B -> C, D -> E
9	Visit neighbors F (B visited)	C	[E, F]	{A, B, C, D, E, F}	A -> B -> C -> F, D -> E
10	Dequeue node	E	[F]	{A, B, C, D, E, F}	A -> B -> C -> F, D -> E
11	Visit neighbors (D, F visited)	E	[F]	{A, B, C, D, E, F}	A -> B -> C -> F, D -> E
12	Dequeue node	F	[]	{A, B, C, D, E, F}	A -> B -> C -> F, D -> E
13	Visit neighbors (C, E visited)	F	[]	{A, B, C, D, E, F}	A -> B -> C -> F, D -> E
14	Queue empty	-	[]	{A, B, C, D, E, F}	Traversal complete

💡 Queue is empty, all reachable nodes visited

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	Final
Queue	[]	[A]	[]	[B, D]	[D]	[D, C]	[C]	[C, E]	[E]	[E, F]	[F]	[F]	[]
Visited Set	{}	{A}	{A}	{A, B, D}	{A, B, D}	{A, B, C, D}	{A, B, C, D}	{A, B, C, D, E}	{A, B, C, D, E}	{A, B, C, D, E, F}	{A, B, C, D, E, F}	{A, B, C, D, E, F}	{A, B, C, D, E, F}
Current Node	-	A	A	B	B	D	D	C	C	E	E	F	-

Key Moments - 3 Insights

Why do we mark nodes as visited before adding them to the queue?

Marking nodes visited before enqueueing (see step 3 and 5) prevents adding the same node multiple times, avoiding repeated visits and infinite loops.

Why does BFS use a queue instead of a stack?

BFS uses a queue (FIFO) to explore nodes level by level, ensuring neighbors are visited in order of distance from the start, unlike a stack which would explore depth first.

What happens when the queue becomes empty?

When the queue is empty (step 14), it means all reachable nodes have been visited and the BFS traversal is complete.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue state after visiting neighbors of node 'B'?

A [D, C]

B [C]

C [B, D]

D []

💡 Hint

Check step 5 in the execution_table for queue state after visiting neighbors of B.

At which step does the BFS visit node 'E' for the first time?

A Step 9

B Step 7

C Step 5

D Step 3

💡 Hint

Look at the 'Operation' and 'Current Node' columns in execution_table to find when E is added.

If node 'F' was not connected to any node, how would the visited set change?

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

B {A, B, D, E, F}

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

D {A, B, C, D}

💡 Hint

Refer to variable_tracker for visited set and consider connectivity impact on BFS.

Concept Snapshot

BFS (Breadth First Search) explores graph nodes level by level.
Uses a queue to track nodes to visit next.
Marks nodes visited before enqueueing to avoid repeats.
Stops when queue is empty (all reachable nodes visited).
Good for shortest path in unweighted graphs.

Full Transcript

Breadth First Search (BFS) starts at a chosen node and explores all its neighbors before moving to the next level neighbors. It uses a queue to keep track of nodes to visit next. Each node is marked visited before adding to the queue to prevent revisiting. The process continues until the queue is empty, meaning all reachable nodes have been visited. This traversal visits nodes in order of their distance from the start node, making BFS useful for shortest path problems in unweighted graphs.