企业官网建设流程全解析

1. 为什么图这一章总让人心里发虚

聊到数据结构与算法面试，前面数组、链表、栈、队列、哈希表、树这几关，大部分人刷一刷还能扛过去。一到图，画风就变了：题目描述里全是“岛屿”“网络延迟”“课程安排”“单词接龙”，看着像语文阅读理解，写起来又像在拼乐高。更麻烦的是，图不像数组那样有天然的下标顺序，也不像树那样有个稳稳的根，它是一张网，节点之间谁连谁、有没有方向、有没有权重，全得你自己在脑子里先建好模型。

这篇东西就是冲着这个痛点来的。我把图相关的面试要点重新捋了一遍，从“图到底怎么存”到“几大核心算法怎么选”，再到“面试官最爱挖的坑在哪”，尽量用一线刷题和带人的经验把它讲透。适合谁看？如果你已经能写二叉树遍历，但一遇到网格搜索、拓扑排序、最短路就卡壳，那这篇就是给你准备的。如果你基础还不错，也可以拿它当一份查漏补缺的清单，看看自己是不是只记住了模板，却没搞懂什么时候该用哪个。

先说一个我自己的判断：图这一章的面试题，真正考的不是你背了多少代码，而是建模能力和算法选型能力。面试官给你一道题，第一步永远是判断这题能不能抽象成图，第二步才是选 BFS、DFS、拓扑还是最短路。很多人栽就栽在第一步，题目都没翻译成图，就开始硬写，结果越写越乱。

2. 图的存储方式：选错了后面全是坑

图这东西，逻辑上就是“点集 + 边集”。但落到代码里，怎么存直接决定了你后面写起来顺不顺。面试里最常见的就是两种：邻接矩阵和邻接表。别看这俩名字简单，选错了真的会让你在写 BFS 的时候多绕十分钟。

2.1 邻接矩阵：适合稠密图，但别乱用

邻接矩阵就是一个二维数组graph[i][j]，表示从节点 i 到节点 j 有没有边，或者边的权重是多少。它的好处是查询“i 和 j 之间有没有边”是 O(1)，写起来也直观，尤其适合节点数不多、边特别密的场景。

但它的问题也很明显：空间是 O(n²)。如果节点有 10 万个，你开一个 10 万乘 10 万的数组，内存直接爆炸。而且如果图很稀疏，大部分格子都是 0，浪费得让人心疼。我见过有人做网格类题目，网格是 200×200，他非要开一个 40000×40000 的矩阵，结果还没跑就挂了。其实网格题根本不需要显式建图，直接按坐标上下左右走就行。

提示：邻接矩阵适合节点数在几百以内、且边比较多的图。面试里如果节点数上千，基本可以放弃矩阵，直接上邻接表。

2.2 邻接表：面试里的主力选手

邻接表就是每个节点挂一个列表，列表里存它所有能到达的邻居。用哈希表或者数组套列表都能实现。它的空间是 O(n + m)，n 是节点数，m 是边数，稀疏图下非常省。遍历一个节点的所有邻居也很快，正好是 BFS 和 DFS 需要的操作。

在 Python 里，我一般这么建：

from collections import defaultdict graph = defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) # 无向图才加这一行

在 Java 里就是List<List<Integer>>或者Map<Integer, List<Integer>>。如果是带权图，列表里存的就不是单个节点，而是(邻居, 权重)这样的二元组。

这里有个细节很多人会忽略：有向图和无向图的建图方式不一样。无向图一条边要加两次，有向图只加一次。面试时如果题目说“A 依赖 B”，那通常是一条从 B 指向 A 的边，方向搞反了，拓扑排序直接全错。

2.3 什么时候干脆不建图

这是我想重点强调的一点。很多图论题，尤其是网格类、岛屿类、迷宫类，根本不需要你显式地把图建出来。网格本身就是一张图，每个格子是一个节点，上下左右相邻就是边。你直接用一个visited数组加方向数组[[0,1],[0,-1],[1,0],[-1,0]]就能遍历，省时省力还省内存。

我个人的经验是：只要节点之间的关系是隐式确定的（比如坐标相邻、字符串差一个字母），就优先考虑不建图，直接在原数据结构上做搜索。只有关系是题目额外给的边列表时，才老老实实建邻接表。

3. 两大基础遍历：BFS 和 DFS 到底怎么选

图的遍历是所有图算法的地基。BFS 和 DFS 这两兄弟，代码都不长，但用错场景就是灾难。面试里经常有人问“这题为什么用 BFS 不用 DFS”，答不上来就露馅了。

3.1 BFS：一层一层往外扩，天然适合找最短

BFS 的核心是队列。你把起点扔进队列，然后每次取出一个节点，把它的邻居加进去，直到队列空。它的特点是按层扩散，先访问离起点近的，再访问远的。

这个特性决定了 BFS 最擅长的场景：无权图的最短路径。因为它是按距离一层层扩的，第一次遇到目标节点时，走过的步数一定是最少的。比如“迷宫最短路径”“单词接龙最少变换次数”“腐烂橘子扩散时间”，这些题用 BFS 就是标准答案。

写 BFS 有几个坑：

• 入队时就标记 visited，不要出队才标记。否则同一个节点可能被重复加入队列，复杂度直接退化。
• 层数怎么记录。常见做法是在每轮开始前记录当前队列长度，一次性处理完这一层，层数加一。这样能准确算出最短距离。
• 多源 BFS。有些题起点不止一个，比如“腐烂橘子”里所有烂橘子同时开始扩散。做法是把所有起点一次性入队，然后正常 BFS，效果就是多源同时扩散。

from collections import deque def bfs(start, target, graph): queue = deque([start]) visited = {start} steps = 0 while queue: for _ in range(len(queue)): node = queue.popleft() if node == target: return steps for nxt in graph[node]: if nxt not in visited: visited.add(nxt) queue.append(nxt) steps += 1 return -1

3.2 DFS：一条路走到黑，适合连通性和回溯

DFS 的核心是递归或者栈。它从起点出发，沿着一条路一直走，走不通了再回头。它的特点是深度优先，适合处理连通性、路径枚举、环检测这类问题。

DFS 最典型的应用是求连通分量。比如“岛屿数量”，你遍历每个格子，遇到陆地就 DFS 把整座岛淹掉，岛屿计数加一。还有“朋友圈数量”“省份数量”都是同一个套路。

DFS 的坑也不少：

• 递归深度。如果图很大，递归可能爆栈。面试时如果节点数上万，最好改成显式栈的迭代写法，或者跟面试官确认递归深度是否可接受。
• visited 的时机。DFS 里通常一进入节点就标记 visited，防止绕圈。
• 回溯和 visited 的区别。这是最容易混的地方。如果题目问“是否存在一条路径”，用 visited 就行，访问过的不用再看。如果题目问“所有路径”或者“排列组合”，那要用回溯，访问完要撤销标记，因为不同路径可以复用同一个节点。

3.3 一张表说清 BFS 和 DFS 的选型

这张表我建议直接记在脑子里。面试时先判断题目属于哪一类，再选算法，比上来就硬写靠谱得多。

4. 拓扑排序：有向无环图的排班艺术

拓扑排序是图论面试里的高频考点，典型题目就是“课程表”“任务调度”“编译顺序”。它的本质是：给一个有向无环图（DAG）的所有节点排个序，保证每条边的起点都排在终点前面。

4.1 Kahn 算法：基于入度的 BFS

Kahn 算法的思路特别符合直觉：先找所有入度为 0 的节点，它们没有前置依赖，可以最先执行。把它们入队，然后依次取出，每取出一个就把它的邻居入度减一，如果某个邻居入度变成 0，说明它的前置都完成了，也入队。最后如果输出的节点数等于总节点数，说明没有环；否则说明有环，无法拓扑排序。

from collections import deque, defaultdict def topo_sort(n, prerequisites): graph = defaultdict(list) indegree = [0] * n for course, pre in prerequisites: graph[pre].append(course) indegree[course] += 1 queue = deque([i for i in range(n) if indegree[i] == 0]) order = [] while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: indegree[nxt] -= 1 if indegree[nxt] == 0: queue.append(nxt) return order if len(order) == n else []

Kahn 算法的好处是顺便能检测环。如果最后输出的节点数不够，就说明有环。这一点在“课程表”题里经常被考到：问你能不能修完所有课，其实就是问图有没有环。

4.2 DFS 版拓扑排序：后序遍历的逆序

DFS 也能做拓扑排序。思路是对每个未访问的节点做 DFS，在递归返回的时候把节点加入结果列表，最后把结果列表反转。这个顺序正好满足拓扑序，因为一个节点的所有后继都先于它被加入列表。

DFS 版的好处是代码短，但检测环稍微麻烦一点，需要用三色标记：白色未访问、灰色正在访问、黑色已完成。如果在 DFS 过程中遇到灰色节点，说明有环。

提示：面试里如果题目只要求判断有没有环，Kahn 算法更直观；如果要求输出拓扑序，两种都行。我个人更推荐 Kahn，因为入度数组的变化过程很清晰，不容易写错。

4.3 拓扑排序的常见变体

拓扑排序不只是“排个序”这么简单，面试里经常变形：

• 课程表 II：要求输出任意一个合法顺序，直接返回 Kahn 的结果。
• 课程表 III：带权重的课程调度，其实已经不是纯拓扑，而是贪心加优先队列。
• 外星文字典：从单词顺序反推字母顺序，本质是建图加拓扑排序。
• 并行课程：问最少需要几个学期修完，本质是 BFS 的层数。

这些变体的核心都是同一件事：把依赖关系抽象成有向边，然后做拓扑排序。建模建对了，剩下的就是套模板。

5. 最短路径：从无权到带权，算法层层升级

最短路径是图论里最庞大的一个家族，面试里出现的频率极高。但好消息是，面试考察的范围其实有限，主要就三档：无权图、非负权图、以及偶尔出现的负权图。

5.1 无权图：BFS 就够了

无权图的最短路径就是 BFS，前面已经讲过。这里补充一个细节：BFS 求的是边数最少，不是权重最小。如果题目里每条边的代价不一样，BFS 就不适用了。

5.2 非负权图：Dijkstra 是标准答案

Dijkstra 算法解决的是边权非负的单源最短路径。它的核心思想是贪心：每次从还没确定的节点里，选一个当前距离最小的，把它确定下来，然后用它去松弛它的邻居。

朴素版 Dijkstra 是 O(n²)，用优先队列优化后是 O((n + m) log n)。面试里一般写优先队列版。

import heapq def dijkstra(n, graph, start): dist = [float('inf')] * n dist[start] = 0 heap = [(0, start)] while heap: d, node = heapq.heappop(heap) if d > dist[node]: continue for nxt, w in graph[node]: nd = d + w if nd < dist[nxt]: dist[nxt] = nd heapq.heappush(heap, (nd, nxt)) return dist

Dijkstra 有几个必须记住的点：

• 不能处理负权边。因为贪心策略假设“当前最小的距离不会再被更新”，负权边会打破这个假设。
• if d > dist[node]: continue这行不能省。这是懒删除，防止处理过期的堆元素。
• 稠密图用朴素版可能更快。因为优先队列的 log 因子在边特别多时反而拖后腿。

5.3 负权图：Bellman-Ford 和 SPFA

如果图里有负权边，Dijkstra 就废了，得换 Bellman-Ford。它的思路是对所有边做 n-1 轮松弛，每轮都尝试用每条边去更新距离。n-1 轮之后，如果还能松弛，说明有负环。

Bellman-Ford 的复杂度是 O(nm)，比较慢。它的优化版是 SPFA，用队列来避免无意义的松弛。但 SPFA 在最坏情况下还是 O(nm)，而且面试里考得不多，了解思路即可。

5.4 多源最短路：Floyd 一把梭

如果题目要求任意两点之间的最短路径，而且节点数不多（一般 n ≤ 400），那就上 Floyd。它的核心是三重循环，枚举中间点 k，然后更新所有 i 到 j 的距离。

def floyd(n, dist): for k in range(n): for i in range(n): 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

Floyd 的代码短到离谱，但要注意循环顺序不能乱：k 必须在最外层。因为它的含义是“只允许经过前 k 个节点作为中间点”，k 放里面就错了。

这张表建议背下来。面试时先看题目问的是单源还是多源，再看有没有负权，基本就能锁定算法。

6. 并查集：处理连通性的瑞士军刀

并查集严格来说不算图算法，但它在图论题里出场率极高，尤其是“连通分量”“冗余连接”“岛屿数量 II”这类题。它的核心操作就两个：find（找根）和 union（合并）。

6.1 路径压缩 + 按秩合并

并查集要跑得快，靠的是两个优化：

• 路径压缩：find 的时候，把沿途所有节点直接挂到根上，下次查找就是 O(1)。
• 按秩合并：union 的时候，把矮的树挂到高的树上，避免树退化成链。

两个优化一起用，均摊复杂度接近 O(1)，快得离谱。

class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry = self.find(x), self.find(y) if rx == ry: return False if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx self.parent[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 return True

6.2 并查集 vs DFS：什么时候用哪个

这是很多人纠结的问题。我的经验是：

• 如果图是静态的，一次性给完所有边，DFS 和并查集都行。DFS 代码更直观，并查集更短。
• 如果边是动态加入的，或者要频繁判断连通性，并查集优势明显。因为 DFS 每次都要重新遍历，并查集是增量的。
• 如果题目问“最少加几条边能连通”，并查集几乎是唯一选择。统计连通分量个数减一就是答案。

提示：并查集不支持删边。如果题目有删边操作，得换思路，比如反向加边或者用更复杂的数据结构。

7. 面试高频题型拆解与避坑实录

前面讲的都是工具，这一节讲怎么用。我把图论面试题分成几大类，每类给一个典型题和解题思路，再附上我踩过的坑。

7.1 网格搜索类：岛屿、迷宫、腐烂橘子

这类题的特点是图是隐式的，网格本身就是图。核心套路是遍历每个格子，遇到符合条件的就启动 BFS 或 DFS，同时用 visited 标记防止重复访问。

典型题“岛屿数量”：遍历网格，遇到'1'就计数加一，然后 DFS 把整座岛变成'0'。这样下次就不会重复计数。

典型题“腐烂橘子”：多源 BFS。把所有烂橘子入队，然后一层层扩散，最后看有没有新鲜橘子剩下。

典型题“迷宫最短路径”：BFS，起点入队，每次走上下左右，遇到终点返回步数。

这类题的坑：

• 边界检查。每次走之前都要判断坐标是否越界，否则数组越界直接崩。
• visited 和原数组的关系。有些题可以直接修改原数组当 visited，省空间；有些题不允许修改，就得额外开数组。
• 多源 BFS 的层数。多源 BFS 的层数代表的是“所有源同时扩散的时间”，不是单个源的距离。

7.2 依赖关系类：课程表、任务调度

这类题的核心是拓扑排序。把依赖关系建成有向图，然后跑 Kahn 或 DFS。

典型题“课程表”：问能不能修完所有课，就是问图有没有环。Kahn 算法最后看输出节点数是否等于总数。

典型题“课程表 II”：要求输出顺序，直接返回 Kahn 的结果。

这类题的坑：

• 边的方向。“课程 A 依赖课程 B”意味着 B 指向 A，别搞反。
• 入度数组的初始化。一定要在加边的时候同步更新入度，别漏了。
• 环的判断。Kahn 算法输出节点数不足就是有环，这个判断别忘。

7.3 最短路径类：网络延迟、最小代价

这类题的核心是选对最短路算法。无权用 BFS，非负权用 Dijkstra，多源用 Floyd。

典型题“网络延迟时间”：从某个节点出发，求到所有节点的最短路径，然后取最大值。标准 Dijkstra。

典型题“最小体力消耗路径”：边权是高度差，非负，用 Dijkstra 或者二分加 BFS。

这类题的坑：

• Dijkstra 的懒删除。if d > dist[node]: continue这行一定要写，否则会处理过期元素。
• 优先队列的排序。Python 的 heapq 是小顶堆，存(距离, 节点)元组，自动按距离排序。
• 不可达的情况。如果某些节点不可达，dist 还是无穷大，最后要判断。

7.4 连通性类：朋友圈、冗余连接

这类题的核心是并查集或 DFS。

典型题“冗余连接”：给一堆边，找出一条可以删掉的边，使得剩下的图是一棵树。做法是遍历边，用并查集判断两个端点是否已经连通，如果已经连通，这条边就是冗余的。

典型题“朋友圈数量”：并查集统计连通分量个数。

这类题的坑：

• 并查集的初始化。parent 数组要初始化为自身。
• 路径压缩的递归写法。递归深度可能很大，注意栈溢出。
• 统计连通分量。遍历所有节点，看有多少个不同的根。

7.5 常见问题速查表

这张表是我自己刷题时总结的，基本上图论题出错就这几个原因。面试时如果卡住了，对照这张表排查，能省不少时间。

8. 我个人的刷题顺序和实战建议

最后聊点实在的。图论这块，我建议的刷题顺序是：先网格搜索，再拓扑排序，再最短路，最后并查集。因为网格搜索最直观，不需要建图，容易建立信心；拓扑排序套路固定，练几道就能掌握；最短路算法多，需要理解选型；并查集代码短但细节多，放最后。

刷题的时候，我强烈建议每道题都先问自己三个问题：

1. 这题能不能抽象成图？节点是什么，边是什么？
2. 是有向还是无向？有没有权重？
3. 要求的是连通性、最短路径、还是拓扑序？

这三个问题答清楚了，算法基本就定了。很多人刷题刷得多但进步慢，就是因为只记代码不记选型逻辑，换个题面就懵了。

还有一个经验：图论题一定要动手画图。面试的时候如果允许，在纸上把节点和边画出来，很多隐藏的环、孤立点、方向问题一眼就能看出来。我见过太多人对着屏幕硬想，想了半天没发现图里有个环，画出来三秒就明白了。

提示：面试时如果一时想不出最优解，先写一个能跑的暴力解，比如 DFS 枚举所有路径。面试官通常更看重你的思路和沟通，而不是一上来就写出最优解。先跑通，再优化，这是更稳妥的策略。

图这一章内容确实多，但核心就那么几块：存储、遍历、拓扑、最短路、并查集。把这几块的模板写熟，再理解每种的适用场景，面试里遇到图论题就不会心里发虚了。真正拉开差距的，从来不是谁背的模板多，而是谁能在一堆文字描述里，快速看出那张隐藏的图。