01_图论

图论

邻接表建图

# 邻接表
adj = [[] for _ in range(n)]
# 无向图
adj[u].append(v)
adj[v].append(u)

adj[u].append((v, w))    # 带权重

图论基础：BFS 适合求最短路，DFS 适合遍历/搜索 ## DFS（深度优先搜索）

核心思想

“一条路走到黑，走不通就回头。” DFS 沿着一个方向一直往深处走，直到无路可走，再回退到上一个岔路口尝试另一个方向。可以用 递归 实现。

递归模板

visited = [False] * n

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

# 处理不连通图
for i in range(n):
    if not visited[i]:
        dfs(i)

网格 DFS — LC 200 岛屿数量

https://leetcode.cn/problems/number-of-islands/

给定一个 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。

思路：遍历每个格子，遇到 '1' 就启动一次 DFS 把整座岛”淹掉”（标记为已访问），岛屿计数 +1。

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def dfs(r, c):
        grid[r][c] = '0'          # 先标记当前格子
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                dfs(nr, nc)

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

BFS（广度优先搜索）

核心思想

“逐层扩散，像水波纹一样。” BFS 从起点出发，先访问距离为 1 的节点，再访问距离为 2 的节点，依此类推。因为一层一层扩展，BFS 天然能求最短路径（边权相等时）。用 队列（deque） 实现。

BFS 模板

from collections import deque

visited = [False] * n

def bfs(start):
    q = deque([start])
    visited[start] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)

# 处理不连通图
for i in range(n):
    if not visited[i]:
        bfs(i)

分层 BFS 模板

很多题目需要知道”当前是第几层”（比如求最短距离），用分层写法：

from collections import deque

def bfs_level(start, graph):
    queue = deque([start])
    visited = {start}
    level = 0
    while queue:
        size = len(queue)               # 当前层的节点数
        for _ in range(size):
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        level += 1                       # 一层处理完，层数 +1
    return level

多源 BFS — LC 994 腐烂的橘子

https://leetcode.cn/problems/rotting-oranges/

网格中 0 是空格，1 是新鲜橘子，2 是腐烂橘子。每分钟腐烂橘子会让上下左右的新鲜橘子腐烂。求所有橘子腐烂的最短时间，不可能则返回 -1。

思路：把所有腐烂橘子同时作为 BFS 起点（多源 BFS），一层层向外扩散，每扩一层就是 1 分钟。

from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # 第一步：找出所有腐烂橘子和新鲜橘子数
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))   # 所有腐烂橘子入队
            elif grid[r][c] == 1:
                fresh += 1
    if fresh == 0:
        return 0

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    minutes = 0
    # 第二步：BFS 逐层扩散
    while queue:
        size = len(queue)
        for _ in range(size):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2       # 新鲜 → 腐烂
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    # 最后一轮多加了 1，需要减掉
    return minutes - 1 if fresh == 0 else -1

DFS vs BFS 对比

维度	DFS	BFS
数据结构	栈 / 递归	队列（deque）
遍历顺序	先深后广	先广后深（逐层）
空间复杂度	O(h)，h 为深度	O(w)，w 为最大宽度
能否求最短路径	不能（需额外处理）	天然最短路径
典型场景	路径搜索、连通分量、回溯	最短路径、层序遍历

选择建议： - 求连通性、所有路径、是否可达 → DFS（代码简洁） - 求最短距离、最少步数 → BFS（天然最短） - 网格/树的层序遍历 → BFS

---

拓扑排序

拓扑排序针对有向无环图（DAG），把所有节点排成一条线，使得每条边的起点都排在终点前面。典型场景是任务调度、课程依赖。核心概念是入度（指向该节点的边数），入度为 0 的节点没有前置依赖，可以最先处理。

LC 207 课程表

共 numCourses 门课，prerequisites[i] = [a, b] 表示学 a 之前要先学 b。判断是否能完成所有课程（即图中是否有环）。

思路：BFS 拓扑排序（Kahn 算法）。维护入度表，每次取入度为 0 的节点，处理后将其邻居入度 -1。最终处理节点数等于总数则无环。

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    # 建图 + 统计入度
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for course, pre in prerequisites:
        graph[pre].append(course)   # pre → course
        in_degree[course] += 1
    # 入度为 0 的节点入队
    queue = deque()
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)
    count = 0   # 已处理的课程数
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1        # 删掉这条边
            if in_degree[neighbor] == 0:    # 入度变 0，可以学了
                queue.append(neighbor)
    return count == numCourses   # 全部处理完说明无环

单源最短路径算法

Dijkstra

Dijkstra 算法用于解决单源最短路径问题：在一个边权非负的有向或无向图中，给定一个起点，计算该起点到所有其他节点的最短距离。

def dijkstra(start, n, adj):
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]   # (当前距离, 节点)
    while pq:
        d, u = heapq.headidppop(pq)
        if d > dist[u]:
            continue    # 忽略过时的记录
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Bellman-Ford 算法

Bellman-Ford 是另一种单源最短路径算法，与 Dijkstra 的最大区别在于：它可以处理负权边，并且能够检测图中是否存在负权环（即环的总权重为负数，导致最短路径无下界）。

核心思想

• 对每条边进行 V-1 次松弛操作（V 是顶点数）。

• 松弛：如果 dist[u] + w < dist[v]，则更新 dist[v]。

• 因为最短路径最多包含 V-1 条边（无环），所以 V-1 轮后所有最短距离必然确定。

• 再做一轮：如果还能松弛，说明存在负权环。

def bellman_ford(n, edges, start):
    """
    参数:
        n: 节点数量 (节点编号 0 ~ n-1)
        edges: 边列表，每条边为 (u, v, w)，表示从 u 到 v 权重为 w（有向图）
        start: 源点编号
    返回:
        dist: 列表，dist[i] 表示 start 到 i 的最短距离
        若存在负权环，则返回 None
    """
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0

    # 第 1 步：进行 n-1 轮松弛
    for i in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        # 如果没有更新，可以提前结束（优化）
        if not updated:
            break

    # 第 2 步：检测负权环（第 n 轮还能松弛则存在负环）
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None   # 存在负权环，无法得到最短路径

    return dist

Floyd-Warshall 算法

1. 算法作用

• 计算所有节点对之间的最短路径。

• 可处理负权边（但不能有负权环）。

• 适用于稠密图，节点数通常 ≤ 500。

def floyd_warshall(n, edges, directed=False):
    """
    n: 节点数 (0 ~ n-1)
    edges: 列表 [(u, v, w), ...] 边和权值
    directed: 是否为有向图，默认无向
    返回 dist 矩阵 (n x n)，不相邻时距离为 INF
    """
    INF = float('inf')
    # 初始化距离矩阵
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
        if not directed:
            dist[v][u] = min(dist[v][u], w)
    # Floyd-Warshall 核心三重循环
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:   # 小优化，跳过不可达
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Kruskal（最小生成树）

def kruskal(edges, n):
    edges.sort()
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False

    return sum(w for w, u, v in edges if union(u, v))

---

经典题目

入门

题号	题目	关键点
LC 200	岛屿数量	网格 DFS/BFS 入门
LC 733	图像渲染（Flood Fill）	基础 DFS 染色
LC 617	合并二叉树	树的 DFS

进阶

题号	题目	关键点
LC 994	腐烂的橘子	多源 BFS
LC 695	岛屿的最大面积	DFS + 计数
LC 542	01 矩阵	多源 BFS 求最短距离
LC 207	课程表	拓扑排序判环

挑战

题号	题目	关键点
LC 127	单词接龙	BFS 最短变换路径
LC 210	课程表 II	拓扑排序输出顺序
LC 417	太平洋大西洋水流问题	反向 DFS，两次搜索求交集

---

小结

1. DFS 和 BFS 是图搜索的两大基石，大量题目都是它们的变体。
2. DFS 用递归或栈，擅长路径搜索和连通性判断。
3. BFS 用队列，擅长最短路径和层序遍历；多源 BFS 处理”同时出发”的场景。
4. 网格问题本质就是图问题，四方向移动是固定套路。
5. 拓扑排序用 BFS（Kahn 算法）处理有向无环图的依赖关系。
6. 刷题时先判断是 DFS 还是 BFS 场景，再套模板，最后根据题意调整细节。