BFS & DFS — Graph Traversals

Graph traversal algorithms visit every reachable vertex from a starting node. Two fundamental strategies exist: BFS explores the graph level by level, while DFS explores as deep as possible along each branch.

Breadth-First Search (BFS)

BFS uses a queue (FIFO). It discovers all nodes at distance 1 before distance 2, all at distance 2 before distance 3, and so on.

Graph: A — B — C
       |       |
       D ————— E

BFS from A: A → B → D → C → E

Key guarantee: BFS finds the shortest path (fewest edges) in unweighted graphs.

Applications:

• Shortest path in unweighted graphs
• Finding connected components
• Web crawling (level-by-level link exploration)
• Social network distance (“degrees of separation”)
• Network broadcasting (flooding)

Complexity: Time O(V + E), Space O(V)

Depth-First Search (DFS)

DFS uses a stack (LIFO) or recursion. It follows one path as far as possible, then backtracks.

Graph: A — B — C
       |       |
       D ————— E

DFS from A: A → B → C → E → D

Key properties: DFS reveals tree structure, back edges (cycles), and finish order (used in topological sort).

Applications:

• Cycle detection in graphs
• Topological ordering of DAGs
• Finding strongly connected components (Tarjan/Kosaraju)
• Maze solving and puzzle exploration
• Dependency resolution

Complexity: Time O(V + E), Space O(V)

BFS vs DFS Comparison