Neural Sync Active

Graph Traversal — BFS and DFS

Registry Synced

Graph Traversal — BFS and DFS

860 words

4 min read

Reading compass

Now · 🎯 Learning Objectives

Graph Traversal — BFS and DFS

🎯 Learning Objectives

By the end of this topic, you will be able to:

Implement BFS using a queue data structure
Implement DFS using a stack or recursion
Compare BFS vs. DFS in terms of space, time, and use cases
Apply BFS to find shortest path in unweighted graphs
Apply DFS for cycle detection and connectivity

📋 Prerequisites

Graph Fundamentals — vertices, edges, adjacency list/matrix

📖 Core Content

19.1 Intuition: Two Ways to Explore

Imagine exploring a museum with many rooms connected by corridors.

BFS is like a wave: explore all rooms closest to you first, then move outward. You'd see all rooms 1 step away, then all rooms 2 steps away, etc.
DFS is like exploring one corridor fully before backtracking. You go deep into one wing, then return and try the next.

💡 Why this matters: BFS finds shortest paths in unweighted graphs (like Google Maps for non-weighted roads). DFS is used for topological sorting, cycle detection, and solving mazes.

19.2 Breadth-First Search (BFS)

Algorithm:

Start from source vertex $s$ . Mark $s$ as visited, enqueue it.
While queue is not empty:
- Dequeue vertex $v$
- Visit each unvisited neighbor $w$ of $v$ : mark visited, enqueue $w$
All vertices reachable from $s$ are now visited.


text
BFS(G, s):
  visited[s] = true
  queue.enqueue(s)
  while queue not empty:
    v = queue.dequeue()
    for each neighbor w of v:
      if not visited[w]:
        visited[w] = true
        queue.enqueue(w)

Time complexity:

O(V + E)

with adjacency list,

O(V^2)

with adjacency matrix. Space complexity:

O(V)

for queue + visited array. Applications:

Shortest path in unweighted graphs (the first time BFS reaches a node, it's via the shortest path)
Web crawling
Social network "friend-of-friend" distance
Finding connected components

19.3 Depth-First Search (DFS)

Algorithm (recursive):

Mark current vertex $v$ as visited
Recursively visit each unvisited neighbor


text
DFS(G, v):
  visited[v] = true
  for each neighbor w of v:
    if not visited[w]:
      DFS(G, w)

Algorithm (iterative, using stack):

Push source $s$ onto stack
While stack not empty:
- Pop $v$
- If $v$ not visited: mark visited, push all neighbors Time complexity: $O(V + E)$ with adjacency list. Space complexity: $O(V)$ for stack + visited. Applications:

Topological sorting
Cycle detection
Finding connected components
Solving puzzles/mazes
Detecting bipartite graphs (Diagram)

19.4 Comparison

Feature	BFS	DFS
Data structure	Queue	Stack (or recursion)
Memory	$O(V)$ (keeps entire frontier)	$O(V)$ (keeps one path)
Shortest path	✅ Yes (unweighted)	❌ No
Cycle detection	❌	✅
Topological sort	❌	✅
Connected components	✅	✅
When to use	All paths short, close to source	Deep exploration, need recursion

19.5 Worked Examples

Example 1: BFS on graph

V=\{1,2,3,4\}

, edges

\{(1,2), (1,3), (2,4), (3,4)\}

, start at 1.

Step	Queue	Visiting	Visited Set
1	[1]	-	{1}
2	[2,3]	1	{1,2,3}
3	[3,4]	2	{1,2,3,4}
4	[4]	3	{1,2,3,4}
5	[]	4	{1,2,3,4}

BFS order:

1, 2, 3, 4

Example 2: DFS on same graph, start at 1. DFS order (depends on neighbor order):

1, 2, 4, 3

1, 3, 4, 2

📐 Key Formulas — Summary Table

Metric	BFS	DFS
Time	$O(V+E)$	$O(V+E)$
Space	$O(V)$ (queue)	$O(V)$ (stack)
Finds shortest path	✅	❌
Cycle detection	❌	✅

⚠️ Common Pitfalls

Pitfall 1: Confusing Queue vs. Stack

BFS uses queue (FIFO) — first discovered, first explored. DFS uses stack (LIFO) — last discovered, first explored.

Pitfall 2: Forgetting to Mark Visited Before Enqueueing

In BFS, mark visited when ENQUEUEING, not when dequeuing. Otherwise, duplicate entries cause inefficiency.

Pitfall 3: Infinite Loop in DFS Due to Cycles

Without a visited set, DFS on a graph with cycles will loop forever.

📝 Practice Questions

Q1: For graph with edges {(1,2),(1,3),(2,4),(3,4)}, what's the BFS order from 1?

$1, 2, 3, 4$

$\boxed{1,2,3,4}$ Q2: What data structure does BFS use?

Queue.

$\boxed{\text{Queue}}$ Q3: What data structure does DFS use?

Stack (or recursion).

$\boxed{\text{Stack}}$ Q4: Which algorithm finds shortest path in unweighted graphs?

BFS.

$\boxed{\text{BFS}}$ Q5: Time complexity of BFS on adjacency list?

$O(V + E)$

$\boxed{O(V+E)}$ Q6: Can DFS be used for topological sorting?

Yes — DFS with a stack to record finish times.

$\boxed{\text{Yes}}$ Q7: For a complete graph $K_n$ , how many vertices does BFS visit from any start?

All $n$ vertices.

$\boxed{n}$ Q8: What's the space complexity of BFS in worst case?

$O(V)$ (if all vertices are on the frontier at once).

$\boxed{O(V)}$

🔗 Cross-References

Previous: Graph Fundamentals
Next: DAGs & Topological Sort
Across courses: BSCS1001 Computational Thinking (search algorithms); PDSA (graph algorithms) Join Discord Previous10.1 Graph FundamentalsNext10.3 DAGs & Topological Sorting