Graph
Algorithms

A graph G = (V, E) can be stored as a 2D matrix M[i][j] where entry (i, j) is 1 (or the edge weight) if an edge exists between vertices i and j, and 0 otherwise.

Adjacency list

Each vertex stores a list of its neighbours. The most common representation for sparse graphs.

graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

Edge list

A flat list of (u, v) pairs (optionally with weight). Minimal storage; useful for algorithms like Kruskal's that iterate all edges.

edges = [
    (0, 1), (0, 3),
    (1, 2), (2, 3)
]

Explore all vertices at distance d before any at distance d+1. Uses a queue (FIFO).

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for nb in graph[v]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return order

Applications

• Shortest path in unweighted graphs
• Level-order traversal
• Connected components in undirected graphs
• Bipartite checking
• Web crawlers, social-network degree separation

Explore as deep as possible along each branch before backtracking. Uses a stack (LIFO) — or recursion.

def dfs(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        order.append(v)
        for nb in reversed(graph[v]):
            if nb not in visited:
                stack.append(nb)
    return order

Recursive variant

def dfs_rec(graph, v, visited=None):
    if visited is None:
        visited = set()
    visited.add(v)
    for nb in graph[v]:
        if nb not in visited:
            dfs_rec(graph, nb, visited)
    return visited

Applications

• Topological sorting
• Cycle detection
• Strongly connected components
• Maze solving & puzzle search
• Articulation points and bridges

Edge classification (directed graphs)

A linear ordering of vertices in a DAG (directed acyclic graph) such that for every directed edge u → v, vertex u comes before v.

Kahn's algorithm (BFS)

from collections import deque

def kahn(graph, n):
    indeg = [0] * n
    for u in range(n):
        for v in graph[u]:
            indeg[v] += 1
    queue = deque(v for v in range(n)
                    if indeg[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    if len(order) != n:
        raise ValueError("Cycle detected")
    return order

DFS-based approach

def topo_dfs(graph, n):
    visited = [False] * n
    stack = []
    def dfs(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)
    for v in range(n):
        if not visited[v]:
            dfs(v)
    return stack[::-1]

Applications

• Build system dependency resolution (Make, Gradle)
• Course prerequisite scheduling
• Task scheduling with precedence constraints
• Spreadsheet cell evaluation order
• Package manager install ordering

Undirected graphs

A connected component is a maximal set of vertices such that there is a path between every pair. Finding all components: run BFS/DFS from each unvisited vertex.

def connected_components(graph, n):
    visited = [False] * n
    components = []
    for v in range(n):
        if not visited[v]:
            comp = []
            stack = [v]
            while stack:
                u = stack.pop()
                if visited[u]:
                    continue
                visited[u] = True
                comp.append(u)
                for nb in graph[u]:
                    if not visited[nb]:
                        stack.append(nb)
            components.append(comp)
    return components

Time: O(V + E) — Space: O(V)

Union-Find alternative

Disjoint Set Union (DSU) with path compression and union by rank achieves near-constant time per operation.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(
                self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices where every vertex is reachable from every other vertex in the set.

Kosaraju's algorithm

1. Run DFS on the original graph; record finish order
2. Transpose the graph (reverse all edges)
3. Run DFS on the transpose in reverse finish order
4. Each DFS tree in step 3 is one SCC

def kosaraju(graph, n):
    # Step 1: finish order via DFS
    visited, order = [False]*n, []
    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]: dfs1(v)
        order.append(u)
    for v in range(n):
        if not visited[v]: dfs1(v)
    # Step 2: transpose
    rev = [[] for _ in range(n)]
    for u in range(n):
        for v in graph[u]: rev[v].append(u)
    # Step 3: DFS on transpose
    visited = [False]*n
    sccs = []
    def dfs2(u, comp):
        visited[u] = True
        comp.append(u)
        for v in rev[u]:
            if not visited[v]: dfs2(v, comp)
    for u in reversed(order):
        if not visited[u]:
            c = []
            dfs2(u, c)
            sccs.append(c)
    return sccs

Tarjan's algorithm

Single-pass DFS using a stack and low-link values. More efficient in practice — no need to transpose the graph.

def tarjan(graph, n):
    idx = [0]
    stack, on_stack = [], [False]*n
    index = [-1]*n
    lowlink = [0]*n
    sccs = []
    def strongconnect(u):
        index[u] = lowlink[u] = idx[0]
        idx[0] += 1
        stack.append(u)
        on_stack[u] = True
        for v in graph[u]:
            if index[v] == -1:
                strongconnect(v)
                lowlink[u] = min(
                    lowlink[u], lowlink[v])
            elif on_stack[v]:
                lowlink[u] = min(
                    lowlink[u], index[v])
        if lowlink[u] == index[u]:
            comp = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                comp.append(w)
                if w == u: break
            sccs.append(comp)
    for v in range(n):
        if index[v] == -1:
            strongconnect(v)
    return sccs

Directed graphs — DFS colouring

Track three states: WHITE (unvisited), GREY (in current DFS path), BLACK (fully processed). A back edge to a GREY vertex indicates a cycle.

def has_cycle_directed(graph, n):
    WHITE, GREY, BLACK = 0, 1, 2
    colour = [WHITE] * n

    def dfs(u):
        colour[u] = GREY
        for v in graph[u]:
            if colour[v] == GREY:
                return True   # back edge
            if colour[v] == WHITE:
                if dfs(v):
                    return True
        colour[u] = BLACK
        return False

    return any(colour[v] == WHITE
               and dfs(v)
               for v in range(n))

Undirected graphs

Simpler: during DFS, if a neighbour is already visited and is not the parent, there is a cycle.

def has_cycle_undirected(graph, n):
    visited = [False] * n

    def dfs(u, parent):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                return True
        return False

    return any(not visited[v]
               and dfs(v, -1)
               for v in range(n))

A graph is bipartite if its vertices can be coloured with two colours such that no edge connects two vertices of the same colour. Equivalently: the graph contains no odd-length cycle.

BFS 2-colouring

from collections import deque

def is_bipartite(graph, n):
    colour = [-1] * n
    for start in range(n):
        if colour[start] != -1:
            continue
        colour[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if colour[v] == -1:
                    colour[v] = 1 - colour[u]
                    queue.append(v)
                elif colour[v] == colour[u]:
                    return False
    return True

Time: O(V + E) — same as a single BFS/DFS pass.

Applications

• Job assignment problems (workers ↔ tasks)
• Graph colouring with 2 colours
• Stable matching (Gale-Shapley)
• Conflict-free scheduling
• Network flow modelling

Definitions

An articulation point (cut vertex) is a vertex whose removal disconnects the graph. A bridge (cut edge) is an edge whose removal disconnects the graph.

Tarjan's bridge-finding

def find_bridges(graph, n):
    disc = [-1] * n
    low = [-1] * n
    timer = [0]
    bridges = []
    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in graph[u]:
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent:
                low[u] = min(low[u], disc[v])
    for v in range(n):
        if disc[v] == -1:
            dfs(v, -1)
    return bridges

Key insight: low-link values

For each vertex u, low[u] is the smallest discovery time reachable from the subtree rooted at u (including back edges).

Applications

• Network reliability analysis — single points of failure
• Critical infrastructure in communication networks
• Biconnected component decomposition
• Router/link failure planning in ISP networks

An Euler path visits every edge exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex.

Existence conditions

Hierholzer's algorithm

def euler_circuit(graph, n):
    # graph: adjacency list (mutable)
    adj = [list(nbrs) for nbrs in graph]
    stack = [0]
    circuit = []
    while stack:
        v = stack[-1]
        if adj[v]:
            u = adj[v].pop()
            # For undirected, also remove
            # reverse edge from adj[u]
            stack.append(u)
        else:
            circuit.append(stack.pop())
    return circuit[::-1]

Time: O(E) — each edge is processed exactly once.

Applications

• DNA fragment assembly (de Bruijn graphs)
• Chinese postman problem
• Circuit board routing
• Network routing optimisation

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that returns to the start vertex.

Euler vs Hamiltonian

Backtracking approach

def hamiltonian_path(graph, n):
    path = [0]
    visited = {0}
    def backtrack():
        if len(path) == n:
            return True
        u = path[-1]
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                path.append(v)
                if backtrack():
                    return True
                path.pop()
                visited.remove(v)
        return False
    if backtrack():
        return path
    return None

Sufficient conditions

Assign colours to vertices so that no two adjacent vertices share the same colour. The minimum number of colours needed is the chromatic number χ(G).

Greedy colouring

def greedy_colour(graph, n):
    colour = [-1] * n
    for u in range(n):
        used = {colour[v] for v in graph[u]
                if colour[v] != -1}
        c = 0
        while c in used:
            c += 1
        colour[u] = c
    return colour

Greedy uses at most Δ + 1 colours, where Δ is the maximum degree. Not always optimal.

Key chromatic numbers

Applications

• Register allocation in compilers (interference graph)
• Exam timetabling — no student has two exams at once
• Map colouring
• Frequency assignment in cellular networks
• Sudoku (9-colouring of the constraint graph)

A graph is planar if it can be drawn on a plane without any edge crossings.

Euler's formula for planar graphs

V - E + F = 2

where V = vertices, E = edges, F = faces (including the outer face).

Corollaries

• For a simple planar graph: E ≤ 3V - 6
• For a bipartite planar graph: E ≤ 2V - 4
• Every planar graph has a vertex of degree ≤ 5

Non-planar graphs

Testing planarity

Applications

• Circuit board layout (PCB routing)
• VLSI chip design
• Geographic information systems
• The four colour theorem applies only to planar graphs

A DAG is a directed graph with no directed cycles. DAGs are the foundation for dependency modelling and scheduling.

Properties

• Has at least one topological ordering
• Has at least one source (in-degree 0) and one sink (out-degree 0)
• Longest path is computable in O(V + E) via topological sort + dynamic programming
• Number of paths between two vertices computable in O(V + E)

Longest path in a DAG

def longest_path_dag(graph, n):
    order = topo_dfs(graph, n)
    dist = [0] * n
    for u in order:
        for v in graph[u]:
            dist[v] = max(dist[v],
                          dist[u] + 1)
    return max(dist)

DAG applications

Key takeaways

• Adjacency lists are the default representation — O(V + E) space, efficient neighbour iteration
• BFS finds shortest paths in unweighted graphs; DFS is the workhorse for cycle detection, topological sort, and SCC
• Topological sort only works on DAGs and runs in O(V + E)
• Tarjan's and Kosaraju's find SCCs in linear time
• Bridges and articulation points identify single points of failure in networks
• Graph colouring is NP-hard for k ≥ 3 but greedy heuristics work well in practice
• Euler paths are tractable (O(E)); Hamiltonian paths are NP-complete
• Most interview graph problems reduce to BFS or DFS with a creative state definition

Recommended reading