9. Graphs

What Is a Graph?

A graph consists of vertices (nodes) and edges (connections) between them. Unlike trees, graphs can have cycles and don't have a single root.

Types:

• Directed: edges have a direction (Twitter follows — you follow someone doesn't mean they follow you)
• Undirected: edges go both ways (Facebook friends — mutual)
• Weighted: edges have a cost/distance (road network with distances)

Real-world graphs:

• Social networks — users as nodes, friendships as edges
• Navigation — cities as nodes, roads as weighted edges
• Package dependencies — packages as nodes, requires as directed edges
• Web pages — pages as nodes, hyperlinks as edges (Google's PageRank)

---

9.1 Graph Representation

from collections import defaultdict

# --- Adjacency List (most common — good for sparse graphs) ---
graph: dict[str, list[str]] = defaultdict(list)
# Add edges
graph["A"].append("B")
graph["A"].append("C")
graph["B"].append("D")
graph["C"].append("D")
graph["D"].append("E")

# Undirected: add both directions
def add_edge_undirected(g, u, v):
    g[u].append(v)
    g[v].append(u)

# Weighted graph: store (neighbour, weight) tuples
weighted: dict[str, list[tuple[str, int]]] = defaultdict(list)
weighted["A"].append(("B", 4))
weighted["A"].append(("C", 2))
weighted["C"].append("B", 1)

# --- Adjacency Matrix (good for dense graphs, small n) ---
n = 5
adj_matrix = [[0] * n for _ in range(n)]
adj_matrix[0][1] = 1   # edge from 0 to 1
adj_matrix[1][0] = 1   # undirected

---

9.2 Depth-First Search (DFS)

Idea: Go as deep as possible along a path before backtracking. Like exploring a maze — always take a new corridor before turning back.

from collections import defaultdict

def dfs(graph: dict, start: str) -> list[str]:
    """Return all nodes reachable from start via DFS."""
    visited = set()
    order   = []

    def explore(node: str) -> None:
        if node in visited:
            return
        visited.add(node)
        order.append(node)
        for neighbour in graph[node]:
            explore(neighbour)

    explore(start)
    return order

# Iterative DFS (avoids recursion limit for large graphs)
def dfs_iterative(graph: dict, start: str) -> list[str]:
    visited = set()
    stack   = [start]
    order   = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                stack.append(neighbour)
    return order

# Use case: check if a path exists between two nodes
def has_path(graph, src, dst, visited=None) -> bool:
    if visited is None: visited = set()
    if src == dst: return True
    visited.add(src)
    for nb in graph[src]:
        if nb not in visited and has_path(graph, nb, dst, visited):
            return True
    return False

---

9.3 Breadth-First Search (BFS)

Idea: Explore all neighbours at the current depth before going deeper. Like ripples in a pond — level by level.

Key advantage: BFS finds the shortest path (in terms of number of edges) in an unweighted graph.

from collections import deque

def bfs(graph: dict, start: str) -> list[str]:
    """Return nodes in BFS order."""
    visited = {start}
    queue   = deque([start])
    order   = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

def shortest_path_bfs(graph: dict, start: str, end: str) -> list[str]:
    """Return shortest path from start to end (fewest edges)."""
    if start == end:
        return [start]
    visited = {start}
    queue   = deque([(start, [start])])   # (current_node, path_so_far)
    while queue:
        node, path = queue.popleft()
        for neighbour in graph[node]:
            if neighbour == end:
                return path + [neighbour]
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append((neighbour, path + [neighbour]))
    return []   # no path found

# Grid BFS — common in real problems (maze, island counting)
def count_islands(grid: list[list[str]]) -> int:
    """Count connected groups of '1' in a grid."""
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def bfs_island(r: int, c: int) -> None:
        queue = deque([(r, c)])
        grid[r][c] = "0"   # mark visited by changing to water
        while queue:
            row, col = queue.popleft()
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:   # 4 directions
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"
                    queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                bfs_island(r, c)
                count += 1
    return count

---

9.4 Topological Sort (Directed Acyclic Graphs)

Use when: you need to order tasks where some tasks must come before others.
Real-world: build systems (compile A before B), course prerequisites, package installation order.

from collections import deque

def topological_sort(n: int, prerequisites: list[list[int]]) -> list[int]:
    """
    Given n tasks (0 to n-1) and prerequisites [a, b] meaning "b before a",
    return a valid ordering. Returns [] if a cycle exists.
    """
    in_degree = [0] * n
    graph = defaultdict(list)

    for a, b in prerequisites:
        graph[b].append(a)   # b → a (b must come first)
        in_degree[a] += 1

    # Start with all tasks that have no prerequisites
    queue = deque(node for node in range(n) if in_degree[node] == 0)
    order = []

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

    return order if len(order) == n else []   # empty = cycle detected

print(topological_sort(4, [[1,0],[2,0],[3,1],[3,2]]))  # [0, 1, 2, 3]

---

9.5 Dijkstra's Shortest Path (Weighted Graphs)

import heapq

def dijkstra(graph: dict[str, list[tuple[str, int]]], start: str) -> dict[str, int]:
    """
    Find shortest distance from start to all nodes.
    graph[u] = [(v, weight), ...] — adjacency list with weights.
    """
    distances: dict[str, int] = {start: 0}
    heap = [(0, start)]   # (distance, node)

    while heap:
        dist, node = heapq.heappop(heap)
        if dist > distances.get(node, float("inf")):
            continue   # already found a shorter path

        for neighbour, weight in graph.get(node, []):
            new_dist = dist + weight
            if new_dist < distances.get(neighbour, float("inf")):
                distances[neighbour] = new_dist
                heapq.heappush(heap, (new_dist, neighbour))

    return distances

# Example: road network
roads: dict[str, list[tuple[str, int]]] = {
    "A": [("B", 4), ("C", 2)],
    "C": [("B", 1), ("D", 5)],
    "B": [("D", 1)],
    "D": []
}
print(dijkstra(roads, "A"))
# {'A': 0, 'C': 2, 'B': 3, 'D': 4}

---