Graph algorithms: BFS, DFS and shortest paths

Representing a graph, traversing it breadth-first or depth-first, and choosing between Dijkstra, Bellman-Ford and A*.

Representing a graph

from collections import deque

# Adjacency list: the default. O(V + E) space, fast to iterate neighbours
unweighted = {
    'a': ['b', 'c'],
    'b': ['d'],
    'c': ['d', 'e'],
    'd': ['e'],
    'e': [],
}

# Weighted: each neighbour carries the cost of the edge
weighted = {
    'a': {'b': 4, 'c': 1},
    'b': {'d': 1},
    'c': {'b': 2, 'd': 5},
    'd': {},
}

# Adjacency matrix: O(V^2) space, O(1) edge test, best for dense graphs
nodes = ['a', 'b', 'c', 'd']
index = {n: i for i, n in enumerate(nodes)}
matrix = [[0] * len(nodes) for _ in nodes]
for u, nbrs in weighted.items():
    for v, w in nbrs.items():
        matrix[index[u]][index[v]] = w

BFS and DFS

Both visit every vertex once and both cost O(V + E). Breadth-first uses a queue and expands in rings, so it finds the fewest edges to each vertex. Depth-first uses a stack or recursion and goes as deep as it can, which is what you want for cycles, connected components and ordering.

def bfs(graph, start):
    """Fewest edges from start, in O(V + E)."""
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:            # mark when enqueuing, not when dequeuing
                dist[nxt] = dist[node] + 1
                parent[nxt] = node
                queue.append(nxt)
    return dist, parent

def reconstruct(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

def dfs(graph, start):
    """Iterative: no recursion limit, and the order is easy to control."""
    seen, order, stack = set(), [], [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue                       # pushed more than once, handled here
        seen.add(node)
        order.append(node)
        stack.extend(reversed(graph[node]))   # reversed: visit in listing order
    return order

def connected_components(graph):
    seen, groups = set(), []
    for node in graph:
        if node in seen:
            continue
        component, stack = [], [node]
        while stack:
            cur = stack.pop()
            if cur in seen:
                continue
            seen.add(cur)
            component.append(cur)
            stack.extend(graph[cur])
        groups.append(component)
    return groups

def has_cycle_directed(graph):
    """Three colours: white unvisited, grey on the current path, black finished."""
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {n: WHITE for n in graph}

    def visit(node):
        colour[node] = GREY
        for nxt in graph[node]:
            if colour[nxt] == GREY:
                return True                 # back edge into the current path
            if colour[nxt] == WHITE and visit(nxt):
                return True
        colour[node] = BLACK
        return False

    return any(colour[n] == WHITE and visit(n) for n in graph)

• Marking a vertex as visited when it is enqueued, rather than dequeued, is what keeps BFS linear; marking on dequeue lets the same vertex enter the queue many times.
• Use a stack for depth-first, a queue for breadth-first: the only difference between the two traversals is which end of the container you take from.
• Recursive DFS hits Python's recursion limit near a thousand frames; convert to an explicit stack for large graphs.
• BFS gives shortest paths only when every edge costs the same. With weights, a path with fewer edges can be more expensive.
• Topological order of a DAG comes from DFS finishing times, or from Kahn's algorithm: repeatedly take a vertex with in-degree zero.
• Union-find answers connected components and cycle detection incrementally, which suits streaming edges better than repeated traversals.

Shortest paths

import heapq

def dijkstra(graph, start):
    """Single source, non-negative weights. O((V + E) log V) with a binary heap."""
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float('inf')):
            continue                        # stale entry: a better route was found
        for nxt, weight in graph[node].items():
            nd = d + weight
            if nd < dist.get(nxt, float('inf')):
                dist[nxt] = nd
                parent[nxt] = node
                heapq.heappush(heap, (nd, nxt))
    return dist, parent

def bellman_ford(edges, vertex_count, start):
    """Handles negative weights. O(V * E); detects negative cycles."""
    dist = [float('inf')] * vertex_count
    dist[start] = 0
    for _ in range(vertex_count - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                           # converged early
    for u, v, w in edges:                    # one more pass: still improving?
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError('negative cycle reachable from start')
    return dist

def floyd_warshall(n, edges):
    """All pairs, O(V^3), simple and dense-graph friendly."""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

FAQ

Related

Sorting and searching Arrays, linked lists, stacks and queues

Last refreshed 2026-09-18.