编程面试中的图论实战：tech-interview-handbook 图论速查表与仓库源码实现详解

2026-09-05 22:58:03作者：裘旻烁

本文以 tech-interview-handbook 仓库中的图论速查文档 apps/website/contents/algorithms/graph.md 为主体，系统讲解图的数据结构表示、DFS/BFS/拓扑排序三大搜索算法的完整模板代码与时间复杂度，并结合仓库 experimental/utilities 目录下的 Python/JavaScript 实现源码，剖析模板的变体写法与边界处理细节。读完本文，你将掌握面试中构建图、遍历图、处理环与边界情况的完整方法，可直接复制运行其中的全部模板代码。

图的概念与建模

图（Graph）是由一组对象（称为节点或顶点）构成的数据结构，节点之间可以通过边（edge）相互连接。边可以是有向的，也可以是无向的；边还可以带有可选的权值（此时称为带权图）。原文档对树给出了一个精确的界定：树是满足"任意两个顶点之间恰好存在一条路径、且图中不存在环"的无向图——换句话说，树是一种特殊、不含环的图。

图常用于建模无序实体之间的关系。原文档给出的两个经典例子：

人物之间的朋友关系：每个节点是一个人，节点间的边表示两人是朋友；
地点之间的距离：每个节点是一个地点，边表示两地之间存在通路，边上的权值表示距离。

在仓库的另一篇文档 coding-interview-techniques.md 中，图也被列为一种核心的问题建模手段："如果数据以实体之间的关联关系呈现，你可能可以把问题建模为图，并用某个常见的图算法求解。"

原文档强调的学习目标：熟悉各种图的表示方式、图搜索算法以及它们的时间和空间复杂度。

图的三种表示方式

面试中常见的输入形式是"给出一组边（edges），要求你自己构建图再做遍历"。原文档列出三种常见表示：

邻接矩阵（Adjacency matrix）
邻接表（Adjacency list）
哈希表的哈希表（Hash table of hash tables）

原文档给出了一个明确的面试策略：在算法面试中，"哈希表的哈希表"是最简单、最推荐的方案；邻接矩阵或邻接表在图题中很少被真正要求使用。仓库的实验性笔记 experimental/topics.md 中同样将图论知识点组织为"邻接矩阵 / 邻接表 / 邻接映射"三种表示，并延伸出 Dijkstra、Bellman-Ford、拓扑排序、最小生成树（Prim/Kruskal）、并查集（Union Find）、统计连通分量、强连通分量、二分图判定等进阶主题，可以作为速查表之后的延伸阅读方向。

矩阵形式的图

原文档特别指出：在算法面试中，图常常以 2D 矩阵的形式作为输入给出——矩阵中的每个单元格就是一个节点，每个单元格可以移动到它的上下左右相邻单元格。因此必须熟悉矩阵遍历，并且在遍历矩阵时，始终确保当前位置在矩阵边界之内、且未被访问过。

时间复杂度

以 |V| 表示顶点数，|E| 表示边数，原文档给出的核心算法复杂度如下：

算法	Big-O
深度优先搜索（DFS）	O(\|V\| + \|E\|)
广度优先搜索（BFS）	O(\|V\| + \|E\|)
拓扑排序（Topological sort）	O(\|V\| + \|E\|)

图搜索算法的面试优先级

原文档按面试出现频率对图搜索算法做了三档分级，这个优先级划分非常实用：

常见（Common）：广度优先搜索（BFS）、深度优先搜索（DFS）
不常见（Uncommon）：拓扑排序、Dijkstra 算法
几乎不出（Almost never）：Bellman-Ford、Floyd-Warshall、Prim、Kruskal——原文档直言"你的面试官很可能自己也不太了解这些"。

深度优先搜索（DFS）

DFS 是尽可能沿每条分支深入探索、直到无路可走再回溯的图遍历算法。实现上通常用一个栈来跟踪当前搜索路径上的节点：既可以是隐式的递归栈（见仓库中递归专题），也可以是显式的栈数据结构（见仓库中栈专题）。

矩阵 DFS 完整模板

原文档给出的矩阵 DFS 模板如下，可直接用于岛屿、洪水填充一类题目：

def dfs(matrix):
  # Check for an empty matrix/graph.
  if not matrix:
    return []

  rows, cols = len(matrix), len(matrix[0])
  visited = set()
  directions = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def traverse(i, j):
    if (i, j) in visited:
      return

    visited.add((i, j))
    # Traverse neighbors.
    for direction in directions:
      next_i, next_j = i + direction[0], j + direction[1]
      if 0 <= next_i < rows and 0 <= next_j < cols:
        # Add in question-specific checks, where relevant.
        traverse(next_i, next_j)

  for i in range(rows):
    for j in range(cols):
      traverse(i, j)

模板要点逐条解读：

空图检查：if not matrix: return [] 对应后文 corner cases 中的"空图"情形；
directions 四方向元组：(0, 1) 右、(0, -1) 左、(1, 0) 下、(-1, 0) 上，是矩阵题的通用常量；
visited 集合：进入即标记，避免重复访问——这是防止图上有环时陷入死循环的关键；
边界判断 0 <= next_i < rows and 0 <= next_j < cols：原文档强调的"边界内且未访问"双重保护；
最外层双 for 循环：从每个未访问节点发起遍历，天然支持不连通图（disconnected graphs）。

仓库源码中的 DFS 变体：对角邻接与边界环绕

仓库的实验性工具目录提供了该模板的两个"follow up"变体，文件为 graph_dfs.py：

# Follow up:
# 1) Diagonal cells are considered neighbors
# 2) View the matrix like Earth, right boundary is adjacent to the left boundary, top adjacent to left, etc.
def graph_dfs_diagonals_and_boundary_wrap(matrix):
    rows, cols = len(matrix), len(matrix[0])
    visited = set()
    # Change 1: Add 4 more diagonal directions.
    directions = ((0, 1), (0, -1), (1, 0), (-1, 0), (-1, -1), (1, 1), (1, -1), (-1, 1))
    def dfs(i, j):
        if (i, j) in visited:
            return
        visited.add((i, j))
        for direction in directions:
            # Change 2: No more boundary, use modulo to allow traversal that exceed boundaries to wrap around.
            next_i, next_j = (i + direction[0] + rows) % rows, (j + direction[1] + cols) % cols
            dfs(next_i, next_j)

    for i in range(rows):
        for j in range(cols):
            dfs(i, j)

与速查表模板相比，只有两处修改，恰好覆盖了面试中常见的两个进阶要求：

变体 1——对角线也算邻居：把 directions 从 4 个扩展为 8 个方向；
变体 2——边界环绕（wrap around）：不再做越界检查，而是用 (i + direction[0] + rows) % rows 这样的取模运算让越界坐标自动绕回矩阵另一端。注意取模前先加 rows/cols，是为了保证负数坐标取模后仍为合法下标。

这个源文件同时印证了速查表模板的正确性：主函数最后直接以 3x4 的矩阵调用 graph_dfs 做验证。

广度优先搜索（BFS）

BFS 从某节点出发，先探索当前深度的所有节点，再进入下一深度层。实现上通常用一个队列跟踪"已遇到但尚未探索"的节点（见仓库中队列专题）。

矩阵 BFS 完整模板

from collections import deque

def bfs(matrix):
  # Check for an empty matrix/graph.
  if not matrix:
    return []

  rows, cols = len(matrix), len(matrix[0])
  visited = set()
  directions = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def traverse(i, j):
    queue = deque([(i, j)])
    while queue:
      curr_i, curr_j = queue.popleft()
      if (curr_i, curr_j) not in visited:
        visited.add((curr_i, curr_j))
        # Traverse neighbors.
        for direction in directions:
          next_i, next_j = curr_i + direction[0], curr_j + direction[1]
          if 0 <= next_i < rows and 0 <= next_j < cols:
            # Add in question-specific checks, where relevant.
            queue.append((next_i, next_j))

  for i in range(rows):
    for j in range(cols):
      traverse(i, j)

与 DFS 模板逐段对照，可以清楚看到两者的一一对应关系：DFS 的"递归 + visited 前置检查"对应 BFS 的"出队 + 出队时检查"；DFS 沿调用栈深入，BFS 则通过 queue.append 将邻居全部入队、逐层推进。

为什么必须用双端队列而不是数组

原文档在模板前特别警告：必须使用双端队列（deque）而不是数组/Python list。原因是双端队列的出队操作是 O(1)，而数组从头弹出元素是 O(n)。这个选择会直接影响整体复杂度：如果错误地使用 list.pop(0)，BFS 的总复杂度会从 O(|V| + |E|) 退化。

原文档还附有一段重要说明（info box）：虽然示例中 DFS 用递归实现，但它同样可以用与 BFS 类似的迭代方式实现。两种算法的本质区别在于底层数据结构——BFS 用队列，DFS 用栈；而 Python 的 deque 类既可以当栈用（append + pop），也可以当队列用（append + popleft），一份代码可覆盖两种需求。

拓扑排序（Topological Sort）

有向图的拓扑排序（或称拓扑序）是对顶点的一种线性排列，使得对每条从 u 指向 v 的有向边 uv，u 都排在 v 之前。更精确地说，拓扑排序是一种图遍历，其中每个节点 v 只在它的所有依赖节点都访问过之后才被访问。

典型应用场景：

任务/作业调度：任务之间存在依赖关系。任务用顶点表示，若任务 x 必须在任务 y 开始前完成，则存在从 x 到 y 的边；
大学选课：课程之间存在先修（pre-requisite）依赖。

入度 + 队列的标准实现

原文档给出的完整实现中，边是二元组数组，且约定第一个值依赖于第二个值（即 [node_id, pre_id] 表示 node_id 需要先完成 pre_id）：

def graph_topo_sort(num_nodes, edges):
    from collections import deque
    nodes, order, queue = {}, [], deque()
    for node_id in range(num_nodes):
        nodes[node_id] = { 'in': 0, 'out': set() }
    for node_id, pre_id in edges:
        nodes[node_id]['in'] += 1
        nodes[pre_id]['out'].add(node_id)
    for node_id in nodes.keys():
        if nodes[node_id]['in'] == 0:
            queue.append(node_id)
    while len(queue):
        node_id = queue.popleft()
        for outgoing_id in nodes[node_id]['out']:
            nodes[outgoing_id]['in'] -= 1
            if nodes[outgoing_id]['in'] == 0:
                queue.append(outgoing_id)
        order.append(node_id)
    return order if len(order) == num_nodes else None

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

算法分四步，值得逐步理解：

建图：为每个节点初始化 in（入度计数）与 out（出边集合）；对每条边 [node_id, pre_id]，node_id 的入度加一，pre_id 的出边集合中加入 node_id；
入队零入度节点：所有没有前置依赖的节点直接可开始处理；
BFS 式消减：每次取出一个节点，将其所有后继的入度减一；后继入度归零时入队；
成环检测：若最终 order 长度不等于 num_nodes，说明图中存在环（有环的图不可能有拓扑序），返回 None。

仓库源码中的两种实现细节差异

仓库在实验性目录中维护了该算法的 Python 与 JavaScript 两份实现，可以对照阅读：

graph_topo_sort.py（Python 版）
graphTopoSort.js（JavaScript 版，使用 Map + Set 建模）

从源码结构看，Python 实验版与速查表版有一处值得注意的差异：速查表用 queue.popleft()（FIFO，队列语义），而 Python 实验版用的是 queue.pop()（LIFO，栈语义）——两者都产生合法的拓扑序，只是节点间的具体顺序可能不同；这恰好说明拓扑序在"零入度节点同时就绪"时并不唯一。JavaScript 版则用 queue.shift() 取队首，保持队列语义，且在检测到环时返回空数组 []（Python 版返回 None）。以文档中的例子 graph_topo_sort(4, [[0, 1], [0, 2], [2, 1], [3, 0]]) 验证，两份实现均能输出合法的拓扑序。

面试注意事项与边界情况

原文档列出的两条面试中要警惕的陷阱：

看似树状的图很可能允许环，朴素的递归解法会失效。此时必须处理环：遍历时维护一个已访问节点集合；
务必正确跟踪已访问节点、保证每个节点最多访问一次，否则代码可能陷入无限循环。

原文档同时列出了必须覆盖的边界情况（corner cases）：

空图（empty graph）
只有 1 个或 2 个节点的图
不连通图（disconnected graphs）
含环的图（graph with cycles）

对照速查表中的三个模板可以发现，这些边界已被结构性地覆盖：开头的 if not matrix: return [] 处理空图；最外层双 for 循环从每个未访问节点重启遍历，天然处理不连通图；visited 集合处理含环图。面试时把这三类保护机制写进解法，是加分项。

补充：用并查集统计连通分量

仓库中还提供了一份与图论紧密相关的工具实现 union_find.py——**并查集（Union-Find）**数据结构，它是"统计连通分量个数"一类题目的另一种经典解法（对应实验笔记 topics.md 中的 "Count connected components in a graph"）：

parents = [0, 1, 2, 3, 4, 5, 6] # parent[i] is the parent of i
weights = [1, 1, 1, 1, 1, 1, 1]

def find_root(parents, p):
    '''Average: O(log n)'''
    root = p
    while parents[root] != root:
        root = parents[root]
    # Flatten tree
    while parents[p] != p:
        parents[p], p = root, parents[p]
    return root

def union(parents, p, q):
    '''Average: O(log n)'''
    p = find_root(parents, p)
    q = find_root(parents, q)
    # Link the smaller node to the larger node
    if weights[p] > weights[q]:
        parents[q] = p
        weights[p] += weights[q]
    else:
        parents[p] = q
        weights[q] += weights[p]

实现要点：find_root 沿父指针上溯到根，并在回溯时做路径压缩（Flatten tree）；union 按规模（weights）归并，让小树的根挂到大树的根下，两者配合使 find/union 的平均复杂度保持 O(log n)。当 DFS/BFS 与并查集都可选时，前者更通用，后者在需要动态合并与查询的场景更合适。

练习题清单

以下题目清单完整继承自原文档。仓库的 QuestionGroups.json 中同样维护了 graph 专题的题目分组（如 Flood Fill 标注了 routines: ["matrix", "depth-first-search"]，并标注了预估时长与难度），可交叉参考。

必做题目（Essential）

原文档标注："这些是学习该主题时必练的核心题目。"

Number of Islands（岛屿数量）
Flood Fill（洪水填充）
01 Matrix（01 矩阵）

学习资源与课程

原文档推荐的外部阅读资源（按主题列出，供按标题检索）：

必读（Readings）
- From Theory To Practice: Representing Graphs（basecs，图表示）
- Deep Dive Through A Graph: DFS Traversal（basecs，DFS 遍历）
- Going Broad In A Graph: BFS Traversal（basecs，BFS 遍历）
有余力时再读（Additional, only if you have time）
- Finding The Shortest Path, With A Little Help From Dijkstra（basecs，Dijkstra 最短路）
- Spinning Around In Cycles With Directed Acyclic Graphs（basecs，有向无环图）

文档末尾通过 Docusaurus 组件引入了仓库的 AlgorithmCourses.md，推荐三门课程：

AlgoMonster：由 Google 工程师打造，用数据驱动方式教最高频的题型模式，一次性付费、终身访问；
Grokking the Coding Interview: Patterns for Coding Questions（Design Gurus）：以"题目模式"视角练习推荐题单，支持 Java、Python、C++、JavaScript 多语言练习与样例解答，作者本人即采用"理解模式而非背答案"的方式准备面试；
Master the Coding Interview: Data Structures + Algorithms（Udemy）：高评分面试课，19 小时内容，除算法外还覆盖简历、非技术面与薪资谈判，代码演示使用 JavaScript。

小结

这张图论速查表的核心方法论可以浓缩为四句话：面试建图优先用哈希表的哈希表；矩阵输入的图必须做"边界 + 已访问"双重检查；DFS 用栈（递归或显式栈）、BFS 必须用 O(1) 出队的双端队列；拓扑排序靠"入度 + 零入度队列"，出不了完整序列就说明有环。配合本文从仓库 graph_dfs.py、graph_topo_sort.py、graphTopoSort.js 与 union_find.py 中核实的源码细节，以及必做/推荐题单，即可构成一份可直接执行的图论面试备考路径。

tech-interview-handbook

Curated coding interview preparation materials for busy software engineers

项目地址：https://gitcode.com/GitHub_Trending/te/tech-interview-handbook

登录后查看全文