图论算法面试精讲

可视化演示

动态演示图论算法面试精讲的核心机制，通过输入/处理/存储/输出四种模式展示关键概念与交互流程。

基础入门

如果你今天拿到一张陌生城市的地铁图，你会先看什么？多数人会先看两个东西：站点数量和轨道数量。站点太少的地图很空，轨道太多的地方容易绕晕。图论的第一课就是这个感觉：图由顶点（站点）和边（轨道）组成，我们关心顶点个数 \(V\) 和边数 \(E\)，因为后续所有算法的时间复杂度都围绕它们展开。

从地铁图过渡到数学表达：顶点记作 \(V\)，边记作 \(E\)。边有方向的是有向图，没有方向的是无向图。地铁线路通常是双向的，对应无向图；而“公众号关注关系”“网页链接”是单向的，对应有向图。面试题里还会出现“带权图”，可以理解成每段轨道有不同行驶时长；权值相同或未指定的图就是无权图。

图论里有一条最著名的“握手引理”：所有站点度数之和等于边数的两倍。度就是这个站点连接的轨道数。为什么？因为每一条边都连接两个端点，在计算总度数时恰好被数了两次。

回到地铁比喻：你不需要背公式，只要记住“每段轨道有两个头”。面试时如果题目给了站点和轨道数，优先检查数据规模，再决定用哪种算法。读图如读地图，先看规模，再做选择。

存储选型

一座城市的地铁图有很多种保存方式。最笨的方法是做一块巨大的“全城换乘查询屏”，把每个站点到每个站点是否有轨道都标出来，这叫邻接矩阵。另一种做法是每个站点门口挂一块“本站可直达”的小牌子，这叫邻接表。还有一种是把轨道工程档案一条条列成数组，这叫边集数组。

三种方式各有适用场景。邻接矩阵用二维数组 \(graph[u][v]\) 表示站点 \(u\) 到 \(v\) 是否有边，判断两点是否相邻只需 \(O(1)\)，但空间固定是 \(V^2\)。邻接表为每个顶点保存一个邻居列表，只记录真实存在的边，空间约等于 \(V + 2E\)。边集数组则把所有边按 (起点, 终点, 权值) 存放，特别适合需要按权值排序的算法，比如 Kruskal 最小生成树。

用比喻收尾：查询屏适合站点少、轨道密的“中心城区”；邻接表像每个站台挂一张小卡片，适合铺得很开的地铁网络；边集数组则是施工队的图纸清单。面试时先问自己：“这个图边多不多？” 一句话就能锁定存储方案。

DFS 遍历

想象一位地铁检修员从 1 号线起点出发，沿着一条支线一直往前走，走到尽头后原路退回最近的岔路口，再换另一条支线继续走。这种“一条路走到黑，再回溯”的巡查方式，就是深度优先搜索（DFS）。

DFS 的关键是递归加上回溯。递归函数进入一个顶点后，标记它“已访问”，然后依次访问每一个未访问的邻居。等到所有邻居都处理完，函数自然返回上一层。这个过程可以抽象成下面这个模板：先做决定，再进邻居，最后撤销现场。

回到地铁检修员：他不需要地图，只需要记住“刚才从哪条路来的”，走完所有岔路后整张网的连通情况就清楚了。DFS 在面试中常用于判断连通分量、检测环、求路径存在性，但注意它不擅长找“最短路径”，因为深挖的路线通常不是最短的。

BFS 遍历

如果地铁失火，广播系统会怎么做？它不会沿着一条线路追到底，而是以事发站为圆心，一圈一圈向外通知：先通知直达站，再通知换乘站，再通知更远的站。这种“逐层扩散”的搜索方式，就是广度优先搜索（BFS）。

BFS 的实现核心是队列，先进先出。起点入队；每次从队首弹出一个站点，把它的所有未访问邻居入队；因为队列按进入顺序处理，所以先被发现的站点一定比后发现的站点离起点更近。因此在无权图中，BFS 天然能求出起点到每个点的最短路径长度。

用广播的比喻来理解：BFS 永远先通知“近的人”，再通知“远的人”，所以首次收到通知的路径一定是最少经过站点的路径。面试中，“最短换乘次数”“社交网络几度人脉”“迷宫最少步数”这类题目，都是在考 BFS。

最短路径

坐地铁导航时，你希望 App 告诉你“从当前站到目的地，哪条路线总耗时最少”。如果每条轨道的行驶时间是已知的，这就是带权最短路径问题。最常见的算法有三种：Dijkstra、Bellman-Ford 和 Floyd。

Dijkstra 像一个精明的导航员：它维护一个“当前已知最短用时表”，每次都从尚未确定的站点里挑一个当前距离最小的站点出来，并用它去更新邻居。这个贪心策略要求所有边权非负，否则先选出来的“最小”可能是错的。核心更新操作叫“松弛”：

回到地铁场景：Dijkstra 适合“所有轨道都不会倒贴时间”的正常城市。如果存在负权边——相当于某条线路不仅不耗时还能“倒赚时间”，Dijkstra 就会被绕晕，这时要改用 Bellman-Ford，它会把所有边反复松弛 \(V-1\) 轮。如果面试要求所有站点两两之间的最短路径，则用 Floyd 动态规划，一次算出整个二维距离表。

最小生成树

假设地铁公司要在多个新区之间铺设轨道，要求所有站点连通，且轨道总造价最低。注意，我们不是求“从 A 到 B 怎么走最快”，而是求“把所有站点连成一个整体最少花多少钱”——这就是最小生成树（MST）问题。

Prim 算法像是从一个已连通的“城市组团”出发，每次都从组团外挑一条通向组团的最短边扩进来。Kruskal 算法则把所有边按造价从小到大排序，从便宜到贵一条条挑选，只要不形成环就加入。两者背后共用同一条“切分性质”：把站点分成两组，横跨两组的边里造价最小的那条，一定属于某棵最小生成树。

用修地铁比喻：Prim 是从已开发的城区向外“长”出去，Kruskal 是先把所有候选轨道标好价格，从便宜到贵慢慢合并。面试里只要听到“连通所有点且总代价最小”，就立刻把题目翻译成 MST。

拓扑排序

如果你负责规划一整条地铁线路的施工：必须先挖隧道，再铺轨道，再装信号系统，最后试运行。这些任务之间有明显的前后依赖，不能乱序。把每个任务看作顶点，任务依赖看作有向边，就得到一个有向无环图（DAG）。

拓扑排序就是给 DAG 里的所有任务排出一个合法执行顺序：每条有向边都必须从“先做的事”指向“后做的事”。经典算法是 Kahn 算法：统计每个顶点的入度，把入度为 0 的顶点先输出，并删除它的所有出边，重复这个过程直到所有顶点输出完毕。如果最后还有顶点未被输出，说明图中存在环，任务计划不可执行。

回到施工比喻：拓扑序不是唯一的。比如铺轨道和装信号系统之间如果没有直接依赖，谁先谁后都可以。面试中如果题目提到“依赖关系”“编译顺序”“课程先修”，第一反应就应该是拓扑排序。

面试实战

面试做题就像拿到一张城市地图但不告诉你该坐几号线。你需要快速完成三件事：读题建模、复杂度估算、代码规范。

读题建模是把业务语言翻译成图论语言。“好友推荐”是找邻居；“最少换乘”是 BFS；“物流运费最低”是带权最短路；“所有仓库联通成本最小”是 MST；“课程依赖”是拓扑排序。然后根据数据规模选择算法：如果 \(V\) 只有几十，Floyd 也可以；如果 \(V\) 是十万，必须用堆优化的 Dijkstra 或邻接表 BFS。

回到地铁比喻：优秀的面试者不是记路名，而是拿到地图先确认“有多少站、多少条轨道”，再决定用哪套出行工具。最后还要写出变量清晰的代码：graph、dist、visited 不要随手写成 g、d、vis。算法正确，再加上可读性，才是真正的面试高分答案。

AI 应用场景

Python 演示

import heapq def dijkstra(n, edges, start):    graph = [[] for _ in range(n)]    for u, v, w in edges:        graph[u].append((v, w))        graph[v].append((u, w))     dist = [float('inf')] * n    dist[start] = 0    pq = [(0, start)]     while pq:        d, u = heapq.heappop(pq)        if d > dist[u]:            continue        for v, w in graph[u]:            nd = d + w            if nd < dist[v]:                dist[v] = nd                heapq.heappush(pq, (nd, v))     return dist if __name__ == '__main__':    edges = [        (0, 1, 4),        (0, 2, 1),        (2, 1, 2),        (1, 3, 1),        (2, 3, 5),    ]    print(dijkstra(4, edges, 0))

1. graph = [[] for _ in range(n)]建邻接表，每个顶点对应一个邻居列表。
2. graph[v].append((u, w))无向图要加两条边，有向图只需加一条。
3. dist[start] = 0起点到自己的最短距离是 0。
4. heapq.heappop(pq)每次弹出当前距离最小的未确定顶点。
5. if d > dist[u]: continue这是经典的“懒删除”，跳过已经过期的旧纪录。
6. for v, w in graph[u]遍历当前站点的所有直达邻居。
7. dist[v] = nd发现更短的路线就立刻更新。
8. heapq.heappush(pq, (nd, v))新纪录进入优先队列，等待下一次扩展。

常见误区

面试题