How Graph Algorithms Work — BFS, DFS, Shortest Path, and Topological Sort

Graphs model relationships. Graph algorithms answer questions about those relationships: What's the shortest path? Are there cycles? In what order should tasks be executed? How many separate components exist?

These four algorithms — BFS, DFS, Dijkstra's shortest path, and topological sort — solve the vast majority of graph problems you'll encounter in practice.

BFS — Breadth-First Search

BFS explores a graph layer by layer, visiting all nodes at distance 1, then distance 2, then distance 3. It uses a queue (FIFO):

function bfs(graph, start):
    queue = [start]
    visited = {start}
    while queue is not empty:
        node = queue.dequeue()
        process(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)

Complexity: O(V + E) — visits every node and traverses every edge once.

Key property: BFS finds the shortest path in unweighted graphs (fewest edges). Because it explores layer by layer, the first time it reaches a node is via the shortest path.

Where it's used:

• Shortest path in unweighted networks — how many hops between two routers?
• Web crawling — discover pages level by level from a seed URL.
• Social network distance — degrees of separation between two users.
• Level-order tree traversal — process all nodes at depth 1, then depth 2, etc.
• Finding connected components — BFS from an unvisited node discovers its entire component.

To reconstruct the actual path (not just the distance), store each node's predecessor:

function bfs_path(graph, start, end):
    queue = [start]
    visited = {start}
    parent = {start: null}
    while queue is not empty:
        node = queue.dequeue()
        if node == end:
            return reconstruct_path(parent, end)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.enqueue(neighbor)
    return no_path

DFS — Depth-First Search

DFS explores as deep as possible before backtracking. It uses a stack (LIFO) or recursion:

function dfs(graph, node, visited):
    visited.add(node)
    process(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Complexity: O(V + E) — same as BFS.

Key property: DFS naturally follows paths to their end, making it ideal for problems that require exhaustive exploration or backtracking.

Where it's used:

• Cycle detection — if DFS encounters a node that's already on the current path (not just visited), there's a cycle. This is how build systems detect circular dependencies.
• Topological sort — covered below.
• Path finding in mazes — follow one path until stuck, backtrack, try another.
• Connected components — same as BFS, different traversal order.
• Tree traversal — in-order, pre-order, post-order are all DFS variants.
• Git commit history — git log walks the DAG depth-first.

BFS vs DFS — When to Use Which

	BFS	DFS
Data structure	Queue	Stack / recursion
Exploration order	Layer by layer	Path by path
Finds shortest path?	Yes (unweighted)	No
Memory	O(V) for the frontier	O(V) for the stack
Detects cycles?	Yes (with extra tracking)	Yes (naturally)
Topological sort?	Yes (Kahn's algorithm)	Yes (reverse post-order)

Use BFS when you need shortest paths or level-order exploration. Use DFS when you need cycle detection, topological ordering, or exhaustive search.

Dijkstra's Algorithm — Weighted Shortest Path

BFS finds shortest paths in unweighted graphs. When edges have weights (costs, distances, latencies), you need Dijkstra's algorithm:

function dijkstra(graph, start):
    dist = {start: 0}           // all others: infinity
    pq = min_heap([(0, start)]) // priority queue
    while pq is not empty:
        (d, node) = pq.pop_min()
        if d > dist[node]: continue  // stale entry
        for (neighbor, weight) in graph[node]:
            new_dist = d + weight
            if new_dist < dist.get(neighbor, infinity):
                dist[neighbor] = new_dist
                pq.push((new_dist, neighbor))
    return dist

Complexity: O((V + E) log V) with a binary heap. The log V comes from heap operations.

How it works: always process the unvisited node with the smallest known distance. This greedy choice is correct because all edge weights are non-negative — you can never find a shorter path through a longer intermediate distance.

Limitation: doesn't work with negative edge weights. For negative weights, use Bellman-Ford (O(V × E)) — which is slower but handles the general case.

Where it's used:

• Network routing — routers compute shortest paths to determine where to forward packets. OSPF uses Dijkstra's directly.
• Maps and navigation — driving directions, with edge weights as travel times.
• Game AI — pathfinding on weighted grids (often using A*, a variant of Dijkstra with a heuristic).

Topological Sort — Ordering Dependencies

Given a directed acyclic graph (DAG), topological sort produces an ordering where every edge goes from earlier to later. This is the "safe execution order" — do everything before its dependencies.

Using DFS (reverse post-order):

function topological_sort(graph):
    visited = {}
    order = []
    for node in graph:
        if node not in visited:
            dfs_topo(graph, node, visited, order)
    return order.reverse()

function dfs_topo(graph, node, visited, order):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_topo(graph, neighbor, visited, order)
    order.append(node)  // post-order: add after all descendants

Complexity: O(V + E).

Where it's used:

• Build systems — Cargo, Make, Bazel compile dependencies before dependents.
• Package managers — npm, pip resolve installation order.
• Task scheduling — "task B depends on task A" → A must run first.
• Spreadsheets — cells that reference other cells form a DAG. Recalculation follows topological order.
• Database migrations — migration 003 depends on 002, which depends on 001.
• Compiler optimizations — instruction scheduling respects data dependencies.

If the graph has a cycle, topological sort is impossible — there's no valid ordering. DFS-based topological sort detects this: if you encounter a node that's on the current path (in the recursion stack), it's a cycle.

How These Algorithms Connect

The four algorithms are building blocks:

• BFS answers "what's closest?" — shortest path, nearest neighbors, level discovery.
• DFS answers "what's reachable?" — connected components, cycle detection, exhaustive search.
• Dijkstra answers "what's cheapest?" — optimal routes in weighted networks.
• Topological sort answers "what comes first?" — dependency ordering.

Many real problems combine them. A compiler uses DFS for control flow analysis, topological sort for instruction scheduling, and the resulting code runs on a CPU where Dijkstra's algorithm routes network packets.

Next Steps

This completes the algorithms foundation. From here:

• How Graphs Work — the data structure these algorithms operate on.
• How Indexing Works — HNSW vector search is a graph traversal algorithm.
• How DNS Works — DNS resolution traverses a hierarchical graph.
• How eBPF Works — the kernel verifier walks the instruction graph to prove safety.