Graph Algorithms

After this lesson, you will be able to: Apply BFS and DFS beyond traversal, implement Dijkstra's shortest path, and use topological sort, cycle detection, and union-find for connected components.

This lesson combines the graph structure from the Data Structures sub-track with the algorithmic techniques you have learned. These algorithms solve an enormous range of real problems: routing, scheduling, dependency resolution, and network analysis.

Prerequisites:Greedy Algorithms Graphs

BFS and DFS as problem solvers

You already implemented BFS and DFS as traversals. Their real power is what they compute along the way. BFS from a node finds the shortest path in edges to every other node in an unweighted graph, because it explores in rings. DFS naturally explores entire branches, which makes it the tool for finding connected components, detecting cycles, and ordering dependencies. Most graph problems are a BFS or DFS with extra bookkeeping.

Dijkstra's shortest path (weighted)

Greedy plus a min-heap. The standard answer for weighted shortest paths.

python

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    dist = {start: 0}
    pq = [(0, start)]                 # (distance, node) min-heap
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist.get(node, float('inf')):
            continue                  # stale entry, skip
        for nbr, w in graph[node]:
            nd = d + w
            if nd < dist.get(nbr, float('inf')):
                dist[nbr] = nd
                heapq.heappush(pq, (nd, nbr))
    return dist
# Time O((V + E) log V) with a binary heap. Weights must be non-negative.

Topological sort and cycle detection

Order tasks so every dependency comes first. Used by build tools and schedulers.

python

from collections import deque

def topo_sort(graph):
    # Kahn's algorithm: repeatedly remove nodes with no remaining prerequisites.
    indegree = {n: 0 for n in graph}
    for n in graph:
        for nbr in graph[n]:
            indegree[nbr] += 1
    q = deque([n for n in graph if indegree[n] == 0])
    order = []
    while q:
        n = q.popleft()
        order.append(n)
        for nbr in graph[n]:
            indegree[nbr] -= 1
            if indegree[nbr] == 0:
                q.append(nbr)
    # If order is shorter than the node count, the graph has a CYCLE.
    return order if len(order) == len(graph) else None

Union-find for connected components

Union-find (disjoint set union) tracks which elements belong to the same group as you merge groups. It answers 'are these two nodes connected?' in nearly constant time with two optimizations (path compression and union by rank). It is the go-to for counting connected components, detecting cycles in undirected graphs, and Kruskal's minimum spanning tree. Recognizing 'this is a grouping/connectivity problem' and reaching for union-find is a strong signal.

Common mistakes only experienced devs catch

Using BFS for weighted shortest paths (it ignores weights; use Dijkstra). Running Dijkstra with negative edge weights (it breaks; use Bellman-Ford). Forgetting to skip stale heap entries in Dijkstra, hurting performance. Not detecting cycles in topological sort (if the output is shorter than the node count, there is a cycle). Implementing union-find without path compression and union by rank, losing the near-constant-time guarantee. Reaching for a fancy algorithm when a plain DFS would answer the question.

←Greedy Algorithms

Back to Algorithms

String Algorithms→