Graph Traversals and Shortest Paths

Breadth-first search (BFS)

Explore the graph layer by layer from a source using a queue.

from collections import deque

def bfs(g, s):
    dist = {s: 0}
    parent = {s: None}
    q = deque([s])
    while q:
        u = q.popleft()
        for v in g[u]:
            if v not in dist:          # first discovery = shortest distance
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    return dist, parent

• Time $O(V + E)$ with adjacency lists ($O(V^2)$ with a matrix); space $O(V)$.
• Gives shortest paths in unweighted graphs; the parent pointers form a BFS tree.
• Applications: shortest hops, connected components, bipartiteness (2-colour by BFS layers; an edge inside a layer means an odd cycle), level-order traversal, web crawling, uninformed search in AI (search).

Depth-first search (DFS)

Go as deep as possible, backtracking when stuck. Recursion (or an explicit stack) does the bookkeeping.

def dfs(g, s, seen=None, order=None):
    if seen is None:
        seen, order = set(), []
    seen.add(s)
    order.append(s)                    # pre-order visit
    for v in g[s]:
        if v not in seen:
            dfs(g, v, seen, order)
    return order

• Time $O(V + E)$; recursion depth up to $V$.
• Record discovery/finish times; in a directed graph edges are tree, back, forward or cross edges. A back edge means a cycle.
• Applications: connected components, cycle detection, topological sort, strongly connected components, path existence, maze solving, backtracking.

Topological sorting

A topological order of a DAG lists vertices so every edge goes from earlier to later (task scheduling, build systems, course prerequisites). It exists iff the graph has no directed cycle.

from collections import deque

def topo_sort(g):                           # Kahn's algorithm
    indeg = {u: 0 for u in g}
    for u in g:
        for v in g[u]:
            indeg[v] += 1
    q = deque(u for u in g if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == len(g) else None   # None → cycle

Alternative: run DFS and output vertices in reverse finishing order. Both are $O(V + E)$.

Shortest paths in weighted graphs

Relaxation is the shared primitive: if $d[u] + w(u, v) < d[v]$, set $d[v] = d[u] + w(u, v)$ and $\text{parent}[v] = u$.

Dijkstra's algorithm (non-negative weights)

import heapq

def dijkstra(g, s):                         # g[u] = [(v, w), ...]
    dist = {s: 0}
    pq = [(0, s)]
    done = set()
    while pq:
        d, u = heapq.heappop(pq)
        if u in done:
            continue                        # stale entry
        done.add(u)
        for v, w in g[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

• Greedy: always finalise the closest unfinished vertex. Correct because with non-negative weights no later path can be shorter.
• $O((V + E)\log V)$ with a heap; $O(V^2)$ with an array.
• Fails with negative edges (it may finalise a vertex too early).

Bellman–Ford (negative weights allowed)

Relax every edge $V - 1$ times; a further improvement in round $V$ reveals a reachable negative cycle. $O(VE)$.

Shortest paths in a DAG

Relax edges in topological order: $O(V + E)$, works with negative weights (no cycles to worry about). Negating the weights gives longest paths (critical-path scheduling).

Floyd–Warshall (all pairs)

$d_k[i][j] = \min(d_{k-1}[i][j],\ d_{k-1}[i][k] + d_{k-1}[k][j])$ — allow vertex $k$ as an intermediate. Three nested loops, $O(V^3)$ time, $O(V^2)$ space; handles negative edges; a negative $d[i][i]$ means a negative cycle.

Which algorithm?

Quick revision