Advanced Graphs

Multi-source BFS, bipartite checks, minimum spanning trees, bridges and Euler paths.

After BFS, DFS, topological sort and Dijkstra, a handful of graph techniques cover most of the remaining interview questions: multi-source BFS, bipartite checks, minimum spanning trees, bridges and Eulerian paths. Each has a short template and a clear signal in the problem statement.

This lesson assumes BFS & DFS, Graphs: Topo Sort & Dijkstra and Union-Find.

Multi-source BFS

Signal: "distance from the *nearest* X", or several sources spreading at once (rotting oranges, walls and gates, 0/1 matrix).

Put every source in the queue at the start, at distance 0. BFS then expands from all of them together, and each cell is reached first by its nearest source. That's O(cells), instead of one BFS per source.

from collections import deque

def nearest_zero(grid):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    q = deque()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:
                dist[r][c] = 0
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

Bipartite graphs (two-coloring)

Signal: "split into two groups so that no edge is inside a group", "possible bipartition", "is it a valid two-team assignment".

Color the nodes with BFS or DFS, alternating colors. An edge between two nodes of the same color means the graph isn't bipartite, which also means it has an odd-length cycle. Remember to start a traversal from every uncolored node, because the graph may be disconnected.

def is_bipartite(graph):                 # adjacency list
    color = {}
    for start in range(len(graph)):
        if start in color:
            continue
        color[start] = 0
        stack = [start]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]
                    stack.append(v)
                elif color[v] == color[u]:
                    return False
    return True

Minimum spanning tree

Signal: "connect all the points or cities at minimum total cost".

Kruskal: sort the edges by weight, and add each edge that joins two different components, tracked with union-find. O(E log E). Best for edge lists.
Prim: grow the tree from one node using a heap of the cheapest edges that leave the tree. O(E log V). Best for dense graphs, or points where every pair is connected.

import heapq

def min_cost_connect_points(points):
    n = len(points)
    in_tree, total, heap = set(), 0, [(0, 0)]    # (cost, node)
    while len(in_tree) < n:
        cost, u = heapq.heappop(heap)
        if u in in_tree:
            continue
        in_tree.add(u)
        total += cost
        xu, yu = points[u]
        for v in range(n):
            if v not in in_tree:
                xv, yv = points[v]
                heapq.heappush(heap, (abs(xu - xv) + abs(yu - yv), v))
    return total

Bridges and articulation points (Tarjan)

Signal: "critical connections", or "which single link failure disconnects the network?"

Run a DFS and record each node's discovery time disc[u] and low[u], the earliest discovery time reachable from u's subtree using at most one back edge. A tree edge u → v is a bridge if low[v] > disc[u]: nothing in v's subtree can reach back above v.

def critical_connections(n, connections):
    graph = [[] for _ in range(n)]
    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)
    disc, low, bridges, timer = [-1] * n, [0] * n, [], [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in graph[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    return bridges

For large graphs, convert this to an iterative DFS or raise Python's recursion limit, and mention that you'd do so.

Eulerian paths (Hierholzer)

Signal: "use every edge exactly once", "reconstruct the itinerary from tickets".

A directed Eulerian path exists when at most one node has out-degree − in-degree = 1 (the start), at most one has −1 (the end), and every other node is balanced. Hierholzer's algorithm: DFS, consuming each edge as you use it, and add a node to the route after all its edges are used. Then reverse the route.

from collections import defaultdict

def find_itinerary(tickets):
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)                # pop() gives the smallest destination
    route, stack = [], ["JFK"]
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        route.append(stack.pop())
    return route[::-1]

Other techniques worth recognizing

[!TIP] Practice Rotting Oranges · Is Graph Bipartite? · Possible Bipartition · Min Cost to Connect All Points · Critical Connections · Reconstruct Itinerary · Minimum Height Trees · Swim in Rising Water · Alien Dictionary