Portfolio/Learn/Graph Algorithms: BFS, DFS, Topological Sort & Shortest Paths
Algorithms & DSIntermediate

Graph Algorithms: BFS, DFS, Topological Sort & Shortest Paths

A comprehensive guide to graph traversal, cycle detection, topological ordering, and shortest path algorithms from Dijkstra to Bellman-Ford.

20 min read
March 12, 2026
GraphsBFSDFSDijkstraTopological SortPython

Graph Representations

Graphs can be represented as adjacency lists (space-efficient for sparse graphs), adjacency matrices (fast edge lookup), or edge lists. For most problems, adjacency lists are optimal — O(V + E) space and efficient traversal.

python
# Adjacency list from edge list
def build_graph(edges: list[list[int]], directed=False) -> dict[int, list[int]]:
    graph = {}
    for u, v in edges:
        graph.setdefault(u, []).append(v)
        if not directed:
            graph.setdefault(v, []).append(u)
    return graph

Breadth-First Search (BFS)

BFS explores nodes level by level, using a queue to track the frontier. It guarantees the shortest path in unweighted graphs and is ideal for finding the minimum number of steps between two nodes.

python
from collections import deque

def bfs(graph: dict, start: int) -> list[int]:
    visited = set([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_unweighted(graph: dict, start: int, end: int) -> list[int]:
    """Find shortest path in an unweighted graph using BFS."""
    visited = {start}
    queue = deque([(start, [start])])

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

    return []  # No path exists

Depth-First Search (DFS)

DFS dives deep before backtracking. It's essential for cycle detection, topological sorting, connected components, and exploring all paths. Both recursive and iterative implementations are important to know.

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

    def explore(node):
        visited.add(node)
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                explore(neighbor)

    explore(start)
    return order


def count_connected_components(n: int, edges: list[list[int]]) -> int:
    """Count connected components in an undirected graph."""
    graph = build_graph(edges)
    visited = set()
    components = 0

    for node in range(n):
        if node not in visited:
            components += 1
            stack = [node]
            while stack:
                curr = stack.pop()
                if curr in visited:
                    continue
                visited.add(curr)
                stack.extend(graph.get(curr, []))

    return components

BFS runs in O(V + E) time where V is vertices and E is edges. Space complexity is O(V) for the visited set and queue. DFS has the same complexity but uses O(V) stack space (recursion depth).

Cycle Detection

python
def has_cycle_directed(graph: dict, n: int) -> bool:
    """Detect cycle in a directed graph using DFS coloring."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

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

    return any(color[i] == WHITE and dfs(i) for i in range(n))

Topological Sort (Kahn's Algorithm)

Topological sort orders vertices so every edge goes from earlier to later. It only works on DAGs (directed acyclic graphs). Kahn's algorithm uses BFS with in-degree counting. If the result doesn't include all nodes, the graph has a cycle.

python
def topological_sort(n: int, edges: list[list[int]]) -> list[int]:
    """Kahn's algorithm: BFS-based topological sort."""
    graph = {i: [] for i in range(n)}
    in_degree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # Empty = has cycle

Dijkstra's Shortest Path

Dijkstra's algorithm finds the shortest path in a weighted graph with non-negative edges. It uses a priority queue to always process the closest unvisited node. Time complexity: O((V + E) log V) with a binary heap.

python
import heapq

def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
    """Shortest distances from start. graph[u] = [(v, weight), ...]"""
    dist = {start: 0}
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue
        for v, weight in graph.get(u, []):
            new_dist = d + weight
            if new_dist < dist.get(v, float("inf")):
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dist

Use BFS for unweighted shortest paths. Use Dijkstra for weighted (non-negative) graphs. Use Bellman-Ford when edges can be negative. Use Floyd-Warshall for all-pairs shortest paths.

More Articles