图论入门实战一文搞懂：BFS、DFS、拓扑排序的题型识别与模板

图论听起来吓人，实际工程里到处是它：构建工具解析模块依赖是拓扑排序，社交产品的二度人脉是 BFS 逐层扩展，风控识别团伙是连通分量，地图导航的最短路是带权 BFS 的升级版。入门图论不需要先啃一遍教科书，掌握三套模板——DFS、BFS、拓扑排序——就能覆盖绝大多数面试题与工程场景，关键在于拿到题目时能认出「这是哪一类」，选对遍历方式。

这篇文章按「建图 → 三套模板 → 题型识别」的顺序推进。三道代表题分别对应网格连通分量（岛屿数量）、无权图最短距离、依赖关系排序（课程表），代码全部可运行，复杂度一并推导，最后给一份图论题的高频坑清单。

第一步：建图——邻接表是默认选择

图最通用的内存形态是邻接表：每个节点挂一个「它能直接到达的节点」列表。相比邻接矩阵的 O(V²) 空间，邻接表按边数计费 O(V+E)，对稀疏图（绝大多数现实场景）优势明显；遍历某个节点的邻居时也只需访问它的列表，不用扫一整行。网格类题目（岛屿、迷宫）是特例——每个格子天然与上下左右相连，不需要显式建表，方向偏移数组直接充当邻接表：

# 通用建图：把边列表转成邻接表（Python）
from collections import defaultdict

def build_graph(n: int, edges: list[tuple[int, int]]) -> dict[int, list[int]]:
    graph = defaultdict(list)       # 邻接表：节点 -> 邻居列表
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)          # 无向图两个方向都要登记
    return graph                    # 孤立节点访问时由 defaultdict 兜底为空表

建好图之后，所有遍历模板都在邻接表上工作。接下来三套模板各对应一类问题，判断标准可以记成一句话：问「连通吗、有几块」用 DFS，问「最少几步」用 BFS，问「依赖顺序、有没有环」用拓扑排序。

DFS 模板：岛屿数量与连通分量

「岛屿数量」：二维网格中 1 是陆地、0 是水，求陆地连成几块。每发现一块未访问的陆地，就从它出发把整块陆地进行 DFS 染色，染色的次数就是岛屿数。网格版 DFS 不需要 visited 数组——直接把访问过的格子改成 0，一个存储位同时充当标记：

# 岛屿数量：网格 DFS 求连通分量（Python）
def num_islands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0]) if rows else 0  # 空网格直接返回 0
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))      # 四方向偏移

    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return                      # 越界即终止
        if grid[r][c] != "1":
            return                      # 水域或已访问，返回
        grid[r][c] = "0"                # 就地标记，防止重复访问
        for dr, dc in directions:       # 向四邻扩散，染尽整块陆地
            dfs(r + dr, c + dc)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":       # 发现新岛屿的入口
                count += 1
                dfs(r, c)               # 染掉整块，后续不再重复计数
    return count

DFS 的时间复杂度是 O(V+E)——每个格子（顶点）至多被访问一次，每条边至多触发一次扩散判断。空间上递归栈最坏 O(V)，对应整张图都是连通陆地的情况。值得一提的是，网格规模极大时 Python 的默认递归深度（通常一千层）会触发 RecursionError，这是真实刷题和工程里都会撞上的墙，解决办法是把递归改成显式栈的迭代 DFS，骨架完全同构。

BFS 模板：无权图最短路径

BFS 的结构性优势在「逐层扩展」：从起点出发，队列按距离从近到远出队，第一次到达某节点时经过的步数必然最少——这就是无权图最短路不需要任何额外算法的原因。实现要点只有一条：入队时立即标记 visited，而不是出队时。出队时标记会让同一节点被多个邻居重复入队，队列膨胀、复杂度退化：

# BFS 求无权图最短距离：入队即标记（Python）
from collections import deque

def shortest_path(graph: dict[int, list[int]],
                  start: int, end: int) -> int:
    if start == end:
        return 0
    visited = {start}               # 集合做标记，入队的同时登记
    queue = deque([(start, 0)])     # 元素为 (节点, 距起点的步数)
    while queue:
        node, dist = queue.popleft()  # 先进先出保证按层扩展
        for neighbor in graph[node]:
            if neighbor in visited:
                continue            # 已登记过，跳过防止重复入队
            visited.add(neighbor)   # 入队时标记，杜绝队列膨胀
            if neighbor == end:     # 首次到达即最短，直接返回
                return dist + 1
            queue.append((neighbor, dist + 1))
    return -1                       # 队列耗尽仍未到达，不连通

复杂度同样是 O(V+E)：每个顶点至多入队一次，每条边在出队时被检查一次。若题目要求「每一层的完整信息」（比如二叉树层序遍历、二度人脉数量），把「一次取一个」改成「先取当前队列长度、整层处理完再进下一轮」即可，骨架不变。

拓扑排序：课程表与环检测

依赖类问题的标准建模是有向图：每门课是节点，「先修 B 才能修 A」连一条 B→A 的边。Kahn 算法的思路非常工程化：统计每个节点的入度，把入度为零的节点（无前置依赖）入队，逐个「完成」——完成一个就把它指向的后续节点入度减一，减到零的节点继续入队。最终完成的节点数少于总节点数，说明存在环，有节点永远凑不齐前置条件：

# 课程表：Kahn 算法拓扑排序 + 环检测（Python）
from collections import deque

def can_finish(num_courses: int,
               prerequisites: list[tuple[int, int]]) -> bool:
    graph = defaultdict(list)
    indegree = [0] * num_courses    # 入度表：前置课程数量
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque(i for i in range(num_courses) if indegree[i] == 0)
    finished = 0                    # 已完成（已出队）的课程数
    while queue:
        node = queue.popleft()
        finished += 1               # 出队即视为修完
        for nxt in graph[node]:
            indegree[nxt] -= 1      # 消除一个前置依赖
            if indegree[nxt] == 0:  # 依赖清零，具备修读资格
                queue.append(nxt)
    return finished == num_courses  # 全部修完无环；有剩余必有环

拓扑排序同样是 O(V+E)，边建图时统计入度、遍历时出队减度，各扫一遍。它还有一个隐藏用途：出队顺序本身就是一种合法的课程修读顺序，题目要「返回一个可行顺序」时把 finished 计数换成记录列表即可。

题型识别与避坑总结

1. visited 标记必须在入队时完成。BFS 出队时标记是最高频的错误，轻则队列重复膨胀，重则在稠密图上超时；DFS 没有队列，但也必须在进入节点的第一时间标记，两族模板各自守住「访问一次」的纪律。
2. 网格题先确认能否就地标记。输入网格允许修改时，把已访问格子改值最省空间；不允许修改（例如同一网格多次查询）则退回独立 visited 矩阵，别为了省内存破坏调用方数据。
3. 递归 DFS 在大规模图上要换显式栈。语言默认递归深度普遍在千级，万级节点的链状图必爆栈；迭代化改动极小（栈替代递归调用），值得养成默认习惯。
4. 有向图与无向图的建图要区分登记。无向图每条边登记两次、有向图只登记一次，课程表这类依赖题把方向连反，拓扑结果完全不可用；建图代码务必对照题面「A 依赖 B」的语义逐字核对。
5. 环检测认准拓扑计数或三色标记。Kahn 的 finished 计数法适合「是否存在环 + 求顺序」一体解决；DFS 三色标记（未访问/访问中/已完成）适合顺带求环路径，两者都要求维护完整，只用 visited 二色会在交叉边上误判。
6. 用「最少几步 → BFS、连通几块 → DFS、先后依赖 → 拓扑」做第一反应。这个映射覆盖了入门阶段几乎全部题型，识别对了，剩下的只是把对应模板抄写填空。

图论入门的性价比极高：三套模板、一个建图函数、六条纪律，就能从完全不会到稳定解决多数图论题。真正的进阶（带权最短路、最小生成树、强连通分量）都建立在这套基础遍历的手感之上——先把模板写熟，再谈算法升级，顺序不要反。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。