🔎 How to Explore Networks and Trees — Graph Traversal
Breadth-First Search (BFS) vs Depth-First Search (DFS)
Two ways to visit every node in a graph. BFS explores level by level using a queue. DFS goes as deep as possible using a stack. Watch them race side by side.
CS A-Level Unit 3
🤔 What is graph traversal?
Graph traversal means visiting every node (circle) in a network by following the connections (lines). There are two main strategies: go wide first (BFS) or go deep first (DFS). Each has different strengths!
🍕 Analogy: BFS is like exploring your neighborhood house by house on each street. DFS is like following one road as far as it goes, then backtracking to try a different path!
BFS (Breadth-First)
• Explores level by level — visits all neighbours before going deeper
• Uses a Queue (FIFO) — First In, First Out
• Finds the shortest path (fewest edges) in unweighted graphs
• Good for: finding nearest neighbours, shortest route with equal costs
• Space: O(V) — stores all nodes at current level
DFS (Depth-First)
• Explores as deep as possible before backtracking
• Uses a Stack (LIFO) — Last In, First Out
• Does NOT find the shortest path (finds A path, not the shortest)
• Good for: maze solving, detecting cycles, topological sorting
• Space: O(V) — stores the current path depth