Graph Algorithms for Backend Engineers: BFS, DFS, and Dijkstra

Introduction#

Graph algorithms appear more often in backend engineering than many engineers expect: dependency resolution, shortest path in routing systems, cycle detection in task schedulers, and reachability in access control systems. This post covers BFS, DFS, and Dijkstra with practical backend examples.

Graph Representation#

from collections import defaultdict
from typing import TypeAlias

# Adjacency list: most common for sparse graphs
Graph: TypeAlias = dict[str, list[str]]
WeightedGraph: TypeAlias = dict[str, list[tuple[str, float]]]

# Example: service dependency graph
dependencies: Graph = {
    "api":        ["auth", "database", "cache"],
    "auth":       ["database"],
    "database":   [],
    "cache":      [],
    "worker":     ["database", "queue"],
    "queue":      [],
}

# Example: network topology with latency weights
network: WeightedGraph = {
    "us-east-1": [("eu-west-1", 80), ("ap-south-1", 200)],
    "eu-west-1": [("us-east-1", 80), ("ap-south-1", 150)],
    "ap-south-1": [("us-east-1", 200), ("eu-west-1", 150)],
}

BFS: Breadth-First Search#

BFS explores nodes level by level. Use for: shortest path in unweighted graphs, finding all nodes reachable within N hops, level-order traversal.

from collections import deque

def bfs(graph: Graph, start: str) -> list[str]:
    """Return nodes in BFS order from start."""
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

def shortest_path_bfs(graph: Graph, start: str, end: str) -> list[str] | None:
    """Find shortest path (fewest hops) between start and end."""
    if start == end:
        return [start]

    visited = {start}
    queue = deque([[start]])  # queue of paths

    while queue:
        path = queue.popleft()
        node = path[-1]
        for neighbor in graph.get(node, []):
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])
    return None  # no path

# Find all services reachable from "api" (blast radius of an API outage)
reachable = bfs(dependencies, "api")
print(f"API depends on: {reachable}")

DFS: Depth-First Search#

DFS explores as deep as possible before backtracking. Use for: cycle detection, topological sort, connected components.

def dfs_iterative(graph: Graph, start: str) -> list[str]:
    """Iterative DFS (avoids recursion stack overflow for large graphs)."""
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph.get(node, [])):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

def has_cycle(graph: Graph) -> bool:
    """Detect a cycle using DFS with three states."""
    WHITE, GRAY, BLACK = 0, 1, 2  # unvisited, in progress, done
    color = {node: WHITE for node in graph}

    def dfs(node: str) -> bool:
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:
                return True  # back edge = cycle
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(dfs(node) for node in graph if color[node] == WHITE)

def topological_sort(graph: Graph) -> list[str]:
    """Return nodes in topological order (dependency before dependent)."""
    if has_cycle(graph):
        raise ValueError("Graph has a cycle — cannot topologically sort")

    visited = set()
    result = []

    def dfs(node: str):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    return result[::-1]  # reverse post-order = topological order

# Determine safe startup order for services
startup_order = topological_sort(dependencies)
print(f"Start services in order: {startup_order}")
# Output: ['database', 'cache', 'auth', 'queue', 'api', 'worker']

Dijkstra: Shortest Path with Weights#

Dijkstra finds the shortest weighted path from a source to all other nodes.

import heapq
from typing import Optional

def dijkstra(
    graph: WeightedGraph,
    start: str
) -> tuple[dict[str, float], dict[str, Optional[str]]]:
    """
    Returns:
    - distances: shortest distance from start to each node
    - predecessors: for path reconstruction
    """
    distances: dict[str, float] = {node: float("inf") for node in graph}
    distances[start] = 0
    predecessors: dict[str, Optional[str]] = {node: None for node in graph}

    # Min-heap: (distance, node)
    heap = [(0, start)]

    while heap:
        dist, node = heapq.heappop(heap)

        # Skip if we already found a shorter path
        if dist > distances[node]:
            continue

        for neighbor, weight in graph.get(node, []):
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                predecessors[neighbor] = node
                heapq.heappush(heap, (new_dist, neighbor))

    return distances, predecessors

def shortest_path(
    graph: WeightedGraph,
    start: str,
    end: str
) -> tuple[float, list[str]]:
    """Return (total cost, path) from start to end."""
    distances, predecessors = dijkstra(graph, start)
    if distances[end] == float("inf"):
        return float("inf"), []

    path = []
    node: Optional[str] = end
    while node is not None:
        path.append(node)
        node = predecessors[node]
    return distances[end], path[::-1]

# Find lowest-latency routing between regions
cost, path = shortest_path(network, "us-east-1", "ap-south-1")
print(f"Best path: {' → '.join(path)} (latency: {cost}ms)")

Practical Application: Permission Graph#

def can_access(permission_graph: Graph, user_role: str, required_permission: str) -> bool:
    """Check if user_role can reach required_permission via role inheritance."""
    # BFS from user_role through role hierarchy
    visited = {user_role}
    queue = deque([user_role])

    while queue:
        role = queue.popleft()
        if role == required_permission:
            return True
        for parent_role in permission_graph.get(role, []):
            if parent_role not in visited:
                visited.add(parent_role)
                queue.append(parent_role)
    return False

role_hierarchy = {
    "admin": ["editor", "viewer"],
    "editor": ["viewer"],
    "viewer": [],
}

print(can_access(role_hierarchy, "admin", "viewer"))  # True
print(can_access(role_hierarchy, "viewer", "editor"))  # False

Conclusion#

BFS for shortest paths in unweighted graphs and level-order exploration. DFS for cycle detection, topological sort, and connected components. Dijkstra for shortest weighted paths — the basis for routing, CDN edge selection, and service mesh traffic management. The adjacency list representation with a visited set handles most production use cases efficiently.