AlgorithmsintermediateJuly 1, 2025 · 3 min read

Graph Traversal: BFS, DFS, and Beyond

A comprehensive guide to graph traversal algorithms — BFS, DFS, topological sort, and their real-world applications.

Part 2 of series: Algorithm Fundamentals

Introduction

Graphs are everywhere — social networks, road maps, dependency trees, circuit netlists. The ability to systematically explore a graph is the foundation of countless algorithms.

We will cover the two fundamental traversal strategies and then show how they extend to solve real problems.

Breadth-First Search (BFS)

BFS explores a graph level by level, visiting all neighbors of the current node before moving deeper. It naturally finds shortest paths in unweighted graphs.

from collections import deque
def bfs(graph: dict[int, list[int]], start: int) -> list[int]:

Time complexity: $O(V + E)$ where $V$ is the number of vertices and $E$ the number of edges.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It is the backbone of cycle detection, topological sorting, and strongly connected components.

def dfs(graph: dict[int, list[int]], start: int) -> list[int]:
    visited = set()
    order = []
    def explore(node: int) -> None:
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:

Topological Sort

For a directed acyclic graph (DAG), topological sort produces a linear ordering of vertices such that for every directed edge $u \to v$ , vertex $u$ comes before $v$ .

This is essential for:

Build system dependency resolution
Course prerequisite scheduling
Data pipeline orchestration

The algorithm is a simple modification of DFS:

def topological_sort(graph: dict[int, list[int]]) -> list[int]:
    visited: set[int] = set()
    result: list[int] = []
    def dfs(node: int) -> None:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:

Comparison

Property	BFS	DFS
Data structure	Queue	Stack (call stack)
Shortest path	Yes (unweighted)	No
Space complexity	$O(V)$	$O(V)$
Cycle detection	Possible	Natural
Topological sort	Kahn's algorithm	Post-order reversal

Key Takeaways

BFS is optimal for shortest-path problems in unweighted graphs.
DFS is the foundation for topological sort, SCC, and bridge/articulation-point detection.
Choose the traversal that matches your problem structure — BFS for "nearest" queries, DFS for "reachability" and ordering.

	from collections import deque

	def bfs(graph: dict[int, list[int]], start: int) -> list[int]:

	def dfs(graph: dict[int, list[int]], start: int) -> list[int]:
	visited = set()
	order = []

	def explore(node: int) -> None:
	visited.add(node)
	order.append(node)
	for neighbor in graph[node]:

	def topological_sort(graph: dict[int, list[int]]) -> list[int]:
	visited: set[int] = set()
	result: list[int] = []

	def dfs(node: int) -> None:
	visited.add(node)
	for neighbor in graph[node]:
	if neighbor not in visited: