企业官网建设流程全解析

翻开教材，3.7这一节往往是整门数据结构课程的坎。图的相关算法不像排序、查找那样有一个明确的"套路"，它是在一堆节点和边的关系上做文章，遍历、最短路径、生成树、拓扑排序，每个算法都有自己的适用前提和边界条件。我当年学到这一节的时候，最大的感受是：单独看每个算法都能看懂，一旦做题或者拿到实际场景里，就不知道该用哪个。这篇内容就是围绕图相关的核心算法展开的，从存储结构到遍历，再到最短路径、最小生成树、拓扑排序，最后补一些实战里最容易踩的坑。适合正在啃教材的学生、准备面试的求职者，以及工作中要处理依赖关系或者路径规划这类问题的工程师。这篇的价值在于把"什么时候该用哪个算法"这条线讲透，而不是再复述一遍教科书上的证明过程。

1. 建图先于算法：存储结构选错，后面全白做

图算法里的大多数代码，本质上都是在"遍历邻居"这件事上做文章。所以图的存储方式决定了遍历邻居的开销，也就直接决定了整个算法能不能跑起来。最常见的两种存储结构是邻接矩阵和邻接表，我对这个选择的体会是：很多代码写起来不对，或者复杂度莫名变高，问题都出在这个最容易被忽略的第一步。

1.1 邻接矩阵：简单直观但别乱用

邻接矩阵就是一个二维数组，matrix[i][j] 表示从节点 i 到节点 j 是否有边，或者边的权重是多少。在没有边的位置填 0 或者一个很大的数 INF。它的优点是写起来极其简单，判断任意两个节点是否相连，时间复杂度是 O(1)，这是它最大的卖点。

但它的缺点是空间固定是 V 的平方，这里的 V 是节点数。如果图有 10000 个节点，直接就是 1 亿个格子，每个格子如果是 4 字节的 int，那就是 400 MB 内存起步。这在工程上是不可接受的。所以邻接矩阵只适合节点数非常少（比如几百个以内）、且图本身比较稠密的场景。所谓稠密，就是边的数量接近 V 的平方级别。如果是一张稀疏图，用邻接矩阵就是在用空间换一个根本用不上的"快速判断两点相连"的能力。

我在处理实际数据时几乎没有用过邻接矩阵，因为现实里的图，比如社交网络的关系图、路网、任务依赖图，基本都是稀疏的。每个节点平均连接几个到几十个其他节点，跟总节点数比起来边数少得可怜。这种时候邻接矩阵就是纯粹的浪费。

1.2 邻接表：工程里的默认选择

邻接表的思路是：每个节点维护一个列表，列表里存的是它能到达的邻居。比如节点 0 连到 1、2、3，那就有一个数组或者链表存着 1、2、3。如果需要带权重，就把邻居节点和权重一起存进去。

这么做的好处非常直接：遍历一个节点的所有邻居时，只需要遍历它的列表，总时间复杂度是所有节点的出度之和，也就是 O(E)，E 是边数。内存占用同样只有 O(V + E)，对稀疏图极其友好。

看一个最简单的 Python 建图示例，用列表存邻接表：

# 假设 n 个节点，edges 里是 [u, v] 表示 u 到 v 有一条边 n = 5 graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) # 如果是有向图，上面这一行就够了 # 如果是无向图，还需要加一行：graph[v].append(u)

带权重的话，就把节点和权重的元组存进去：

# [u, v, w] 表示 u 到 v 有一条权重为 w 的边 for u, v, w in edges: graph[u].append((v, w))

这是我的默认写法。在 C++ 里就是vector<vector<int>>或者vector<int> g[N]，思路完全一样。只要没有特殊说明需要频繁判断"任意两点是否相连"，我都会选邻接表。大部分算法题和工程项目里，邻接表的性能都远好于邻接矩阵。

1.3 什么时候需要特殊存储

除了这两种常规方式，还有几个不常见但值得知道的变体。一种是边集数组，就是把所有边直接放在一个数组或者列表里，每条边是一个三元组 (u, v, w)。这种存储方式不关心节点之间的邻接关系，只关心"有哪些边"，所以在 Kruskal 最小生成树算法里会用得比较多，因为它要对边排序。

另一种是链式前向星，这是竞赛圈常用的写法。它本质上是用数组模拟链表，把邻接表实现得更紧凑，遍历速度更快。但对大多数场景来说，用向量或二维列表就够了，没必要牺牲可读性去追求这一点性能。

还有一个很容易被忽略的点：如果节点的编号不是从 0 开始的连续整数，或者节点本身是字符串，那通常需要先做一次离散化，把节点映射成 0 到 V-1 的整数。很多人在做题时直接拿字符串当索引，结果代码写得非常别扭。我一般会用一个哈希表，比如 Python 里的字典，先把所有节点名映射成整数，再开始建图。这个小步骤能省掉后面大量的麻烦。

2. 遍历不只是"走一遍"：DFS与BFS的真正分歧点

图的遍历是几乎所有图算法的基础。DFS（深度优先搜索）和 BFS（广度优先搜索）看起来只是在"走法"上不同，一个往深了走，一个往浅了扩散，但它们在实际应用里的定位差异非常大。我刚开始学的时候以为它们只是顺序不同，后来才发现，选哪个遍历方式，直接决定了你能不能高效解决某类问题。

2.1 用递归还是显式栈：DFS的实现细节

DFS 的思路是：从一个节点出发，沿着一条路径走到尽头，再回头走另一条路径。实现上可以用递归，函数自己调用自己：

def dfs(u, visited, graph): visited[u] = True # 处理当前节点 for v in graph[u]: if not visited[v]: dfs(v, visited, graph)

递归版本写起来最直观，但它有一个隐患：当图的节点数非常大，比如 10 万甚至 100 万的时候，递归深度可能超过语言或运行环境的默认限制，导致栈溢出。Python 的默认递归深度大约是 1000 层，真遇到深链的图，轻轻松松就爆了。这种情况下，要么手动调大递归限制，要么改用显式栈模拟：

def dfs_iterative(start, graph): visited = set() stack = [start] while stack: u = stack.pop() if u in visited: continue visited.add(u) # 处理当前节点 for v in graph[u]: if v not in visited: stack.append(v)

这个版本的顺序会和递归版本略有差异，因为栈是后进先出的，但遍历到的节点集合是一样的。工程上如果需要用 DFS，我一般优先考虑显式栈，省得递归深了出问题。

2.2 BFS与"最短跳数"的天然联系

BFS 用队列实现，一层一层往外扩散。它的一个极其重要的性质是：在无权图（或者说所有边的权重相同）中，BFS 第一次到达某个节点时，走的路径一定是最短的，这里的"最短"指的是经过的边数最少或者跳数最少。

这个性质在很多场景里可以直接拿来用。比如社交网络里计算两个人之间隔着几层关系，再比如迷宫里找从起点到终点的最少步数。只要图是等权的，直接用 BFS 就能拿到最短跳数，根本不需要上 Dijkstra 这种更复杂的算法。Dijkstra 本质上就是"有权版本的 BFS"，先把这条线理解清楚了，后面学 Dijkstra 会顺很多。

BFS 的模板代码很固定：

from collections import deque def bfs(start, graph): visited = [False] * len(graph) dist = [-1] * len(graph) q = deque([start]) visited[start] = True dist[start] = 0 while q: u = q.popleft() for v in graph[u]: if not visited[v]: visited[v] = True dist[v] = dist[u] + 1 q.append(v) return dist

这里的 dist 数组记录每个节点的最短跳数。BFS 第一次碰到节点 v 时，dist[v] 就是最终答案，不需要后续再更新。

2.3 遍历顺序干扰下的visited标记坑

有一个问题我栽过好几次：什么时候标记 visited 才合适？大多数人会在节点入队或入栈时才标记，但更稳妥的是在把邻居加入队列时顺便标记，否则在有些图结构里同一个节点可能被多次放进队列，导致重复处理，虽然最后结果可能没错，但效率会差很多，甚至在某些统计问题里会算出重复的答案。

还有一个常见误区是：DFS 里递归函数的开头已经标记了 visited，但相邻节点在循环里又忘了判断，结果出现循环依赖，栈溢出或者死循环。每次写遍历，我都习惯先想清楚三件事：visited 在哪一步标记、邻居在哪一步判断、有没有可能重复访问。想明白了这三个问题，遍历代码一般不会出大错。

3. 最短路径三件套：Dijkstra、Bellman-Ford、Floyd的取舍

最短路径问题是图算法里最"出圈"的一个，因为它的应用太常见了：地图导航找最快路线、网络路由选择延迟最低的路径、物流系统规划运输成本最低的线路。但最短路径并不是一个算法通吃，单源和多源、有没有负权边、图稠密还是稀疏，这些条件决定了你该从哪个算法下手。

3.1 Dijkstra：贪心在有向非负权图上的胜利

Dijkstra 解决的是"从一个起点到其他所有节点的最短路径"，前提是所有边的权重不能为负数。它为什么不能处理负权？因为它的核心策略是贪心：每次从还没确定最短路的节点里，取出当前距离最小的节点，认定它的最短路已经确定了，然后拿它去更新邻居。

这个策略在非负权图下是安全的，因为任何绕路去更新该节点的路径，都不可能比当前距离更小。但一旦出现负权边，就可能出现一条"先走远路、再被负权边拉回来"的路径，距离反而更小。此时贪心直接失效。我当年在做题时被一道带负权边的题坑过，用了 Dijkstra，结果几乎每条答案都差那么一点点，怎么都想不通，后来才发现是算法选错了。

算法实现上，朴素版 Dijkstra 每次要找最小距离节点，复杂度是 O(V²)。但在稀疏图里，用优先队列优化一下效率会好很多。配合堆的版本，核心代码如下：

import heapq def dijkstra(start, graph, n): INF = 10**18 dist = [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

注意两件事：优先队列里存的是 (距离, 节点)，因为 Python 的堆默认按元组第一个元素排序；第二件事是if d > dist[u]: continue这行的作用。因为一个节点的 dist 可能在入堆之后又被更短的路径更新，堆里会残留一些"过期"的旧距离记录，弹出时发现它不是当前最小值，直接丢弃。没有这行会多处理很多无效节点，但结果依然是对的，只是慢。

3.2 Bellman-Ford：为负权边而生

Bellman-Ford 解决同样的问题，但它允许图中存在负权边。它的思路简单粗暴：对所有边进行松弛操作，所谓松弛，就是看能不能通过当前节点让邻居的距离更小。重复做 V-1 轮，每一轮都尝试用所有边更新距离。在一个没有负环的图里，最短路径的边数最多是 V-1 条，所以 V-1 轮松弛之后，所有节点的最短距离就稳定了。

代码上非常简洁，用上一步提到的边集数组最方便：

def bellman_ford(n, edges, start): INF = 10**18 dist = [INF] * n dist[start] = 0 for _ in range(n - 1): for u, v, w in edges: if dist[u] != INF and dist[u] + w < dist[v]: dist[v] = dist[u] + w # 再试一轮，如果还有更新，说明存在负环 for u, v, w in edges: if dist[u] != INF and dist[u] + w < dist[v]: return None # 存在负环 return dist

很多同学不理解为什么是 V-1 轮。打个比方，最短路的形成就像信息传播，每一轮松弛只保证"信息"在路径上最多往后传一条边。一条路径最多经过 V 个节点，也就是最多 V-1 条边，所以传 V-1 轮，所有最短路里的边都能被覆盖到。如果第 V 轮还能继续更新，说明存在一个永远能让距离变小的环，也就是负环，这时候最短路就没有意义了。

Bellman-Ford 的缺点是慢，复杂度 O(V·E)。在图上很容易超时。它最大的价值其实不是"算最短路"，而是"判断有没有负环"，以及作为一个理论上的兜底方案。

3.3 Floyd：多源最短路径的"暴力美学"

如果要求所有节点对之间的最短路径，Floyd 是最好写的算法，没有之一。三层循环，中间节点 k、起点 i、终点 j，不断更新 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][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]

dist 初始就是邻接矩阵：有边的地方存权重，无边的地方存 INF，自己到自己存 0。Floyd 能处理负权边，只要没有负环就行。它的复杂度是 O(V³)，所以只适合节点数在几百量级的场景，再多就会跑不动。

三个算法怎么选，我的经验是：

最后一行的判断挺反直觉的，很多人觉得堆优化肯定更快。但稠密图里边数接近 V²，堆优化的 O(E·logV) 反而会比 O(V²) 更大。所以算法选型真的要看数据范围，不能无脑堆优化。

4. 造路的学问：Prim与Kruskal如何安全"圈地"

最小生成树解决的问题是：在一个带权无向连通图里，选出一组边，把所有节点连起来，同时让边的总权重最小。这个问题的应用场景非常接地气：铺设电缆连接所有村庄、建设通信基站之间的光缆网络、规划供水管道的最小总长度。它的本质是"用最小的成本把孤岛连成整体"，我管这叫"安全圈地"。

最小生成树有两个经典算法：Kruskal（克鲁斯卡尔）和 Prim（普里姆）。它们思路差异很大，但殊途同归。

4.1 Kruskal：排序加并查集，思路直白

Kruskal 的思路可以概括为：把所有边按权重从小到大排序，然后一条边一条边地看，如果这条边连接的两个节点目前还不属于同一个连通块，就把它选进生成树。

为什么这样选出来的结果一定是最小生成树？这个结论背后是切割定理：在任意一个时刻，把节点分成两块，跨过这两块之间的最短那条边，一定属于某棵最小生成树。Kruskal 每次选的都是当前连接不同连通块的最短边，正好符合切割定理的条件。

实现上最重要的一点是要能快速判断"两个节点是否在同一个连通块"，这就要用到并查集。代码结构大概是：

# 并查集部分 parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra != rb: parent[ra] = rb return True return False # 主流程 edges.sort(key=lambda e: e[2]) mst_weight = 0 for u, v, w in edges: if union(u, v): mst_weight += w

如果最后选出来的边数少于 V-1，说明图不连通，也就不存在覆盖所有节点的生成树。

Kruskal 的时间主要花在排序上，复杂度是 O(E·logE)。它适合边比较稀疏的图，因为排序成本相对可控。

4.2 Prim：从单个点长出一棵树

Prim 的思路不一样：从一个节点出发，维护一个"已经在树里"的集合，然后每次找一条连接树内和树外节点的最短边，把对面的节点加进树里。重复 V-1 次，所有节点就都进树了。

它和 Dijkstra 看起来特别像，区别在于更新的依据不同。Dijkstra 更新的是"到起点的距离"，Prim 更新的是"到当前树集合的最短距离"。

朴素版 Prim 的实现：

def prim(n, graph): INF = 10**18 dist = [INF] * n # 每个节点到已选集合的最短距离 visited = [False] * n dist[0] = 0 mst_weight = 0 for _ in range(n): u = -1 for i in range(n): if not visited[i] and (u == -1 or dist[i] < dist[u]): u = i if u == -1: return None # 图不连通 visited[u] = True mst_weight += dist[u] for v, w in graph[u]: if not visited[v] and w < dist[v]: dist[v] = w return mst_weight

朴素版复杂度是 O(V²)，和邻接矩阵配合起来在稠密图上效果很好。如果想用堆优化，可以像 Dijkstra 那样加优先队列，复杂度到 O(E·logV)，适合稀疏图。

4.3 两种算法在实际工程里的选择依据

很多教材都会说 Kruskal 适合稀疏图、Prim 适合稠密图，这句话在理论上是对的，但工程上还有别的考虑维度。

Kruskal 的优点是算法思路完全不用管图长什么样，只要拿到所有边的列表就能算，而且并查集极好写。它不依赖图的遍历能力，所以很多时候实现成本低。Prim 则必须建立在"从某个节点开始扩散"的模型上，需要能快速找到一个节点它的所有邻居。如果图的存储是邻接表，Prim 天然就好用。

我自己的习惯是：能做边的排序就直接用 Kruskal，简单不容易错。只有当图特别稠密、边数接近完全图的时候，我才考虑用朴素 Prim 来绕开排序的开销。另外还有一个冷门但实用的技巧：如果题目要求输出"最小生成树由哪些边构成"，Kruskal 天然就输出边列表，往往更方便。

5. 拓扑排序不止于排序：从依赖图到任务调度

拓扑排序是图算法里应用最"工程化"的一个。它的场景很明确：你有一堆任务，任务之间有先后依赖关系，比如"先完成 A 才能开始 B"，要求找出一个合法的执行顺序。

把这种依赖关系建模成有向图：每个节点是一个任务，每一条边 A -> B 表示 A 必须在 B 之前完成。如果整个图能够排出一种顺序，让所有边都从"前面的节点"指向"后面的节点"，这种顺序就是拓扑序。

5.1 一个有向无环图才能排出的顺序

拓扑排序的难点在于：并不是所有有向图都有拓扑序。如果图里存在环，比如 A -> B、B -> C、C -> A，那这三个任务互相依赖，永远找不到合法的先后顺序。所以拓扑排序只能作用在有向无环图（DAG）上。

Kahn 算法是最常用的实现方式，思路很好理解：一个节点能被执行，前提是它的所有前驱节点都已经执行过了。换句话说，如果一个节点的入度为 0，它就没有任何前置依赖，可以直接排进顺序。执行完之后，它指向的那些邻居的入度都要减一，减到 0 的邻居就变成了新的可执行节点。

from collections import deque def topo_sort(n, graph): indeg = [0] * n for u in range(n): for v in graph[u]: indeg[v] += 1 q = deque([i for i in range(n) if indeg[i] == 0]) result = [] while q: u = q.popleft() result.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) if len(result) != n: return None # 有环，无法拓扑排序 return result

我特别喜欢 Kahn 算法的一点是，它用队列模拟了一个"就绪队列"的概念，这和操作系统的进程调度、构建系统里的任务调度几乎一一对应。理解了一个，就等于理解了另一个。

5.2 环检测：拓扑排序的真正价值

拓扑排序在很多场景里的最大价值，不是排出一个合法顺序，而是判断"能不能排出来"。如果图里有环，说明任务之间存在循环依赖，整个调度根本无法成立。

回到 Kahn 算法的最后一步：如果排出来的节点数少于总节点数，那就说明有节点永远进不了队列，因为它始终有入度无法清零，也就是存在环。这一步判断非常便宜，却特别有用。

我记得有一次需要处理一批模块的编译顺序，模块之间有一堆互相引用的关系。我一开始直接按名字排序，结果编译时报了一堆循环依赖的错误。后来改成先建依赖图，跑一遍拓扑排序，很清楚地定位到是哪个模块互相引用了，才彻底解决问题。工程上"依赖不能成环"是一个硬约束，拓扑排序就是检测这个约束的利器。

5.3 常见场景：编译顺序、任务编排

拓扑排序的应用远不止课程作业。构建工具里，源文件之间的 include 依赖决定了编译顺序，本质是拓扑排序。包管理器里，库之间的依赖关系要先解析，才能确定安装顺序，这也是拓扑排序。数据流水线里，一个计算任务依赖另一个计算任务的输出，调度系统也要先做拓扑排序。

这类题的一个变形是：如果存在多个合法拓扑序，要求输出字典序最小的那个。做法也很简单，把 Kahn 算法里的普通队列换成优先队列，每次优先取编号最小的入度为 0 的节点。我之前在处理任务编排时用过这个变形，为的是让输出顺序更稳定、更符合直觉。这个小技巧值得记下来。

6. 刷了那么多图，最后还是栽在这些细节上

图算法的大框架学完之后，真正决定代码能不能一次性写对、能不能在时限内跑完的，往往是一些小细节。我把自己反复踩过的坑集中整理了一下，这些细节看似不起眼，但每一条都让我浪费过不少时间。

6.1 用0还是用INF初始化dist数组

最最容易踩的坑，就是距离数组的初始值。如果图里边的权重可能很大，比如 10 的 9 次方，而你把 INF 设成 10 的 6 次方，那在松弛比较dist[u] + w < dist[v]时，u 的可达距离加上 1 亿可能会直接超过 int 的范围，产生溢出，或者让本应更新的路径被错误跳过。

所以我现在的习惯是：INF 至少设成题目给的最大可能距离乘个 2 到 3 倍，用 Python 就直接用10**18，用 C++ 就用LLONG_MAX / 4。用一个足够大的数，比每次猜"够不够大"要稳得多。

另一个细节是：无向图的矩阵初始化时，对角线要设为 0，没有边的位置设为 INF。如果对角线不设 0，Floyd 跑出来的结果会莫名其妙多出一些自环路径的干扰。

6.2 稀疏图和稠密图的最短路实现选择

我在前面提过 Dijkstra 的堆优化和朴素版选择问题，这个坑在工程里会放大得特别明显。有一回我处理一个节点极少但边几乎写满的稠密图，用了堆优化的 Dijkstra，结果发现优先队列里的节点被反复更新，堆里的元素数量膨胀得比预想大很多，虽然最后还是跑完，但效率明显不如朴素版 O(V²) 扫一遍。

反过来说，在 E 接近 V 的稀疏图里，堆优化基本是碾压级别的快。所以选算法之前，请务必先看清楚边的数量级。如果题目没有明确说明 E 的范围，我建议先看节点的数据范围做一个预估：V² 和 E·logV 哪个算起来更小，就选哪个。

6.3 真题拆解：一个地铁换乘问题

接下来用一个综合例子把这些算法串起来。假设给你一张地铁线路图，站台是节点，站与站之间是边，边权是两站之间的通行时间，现在要算从起点站到终点站最短要花多久。

这个题看起来直接套 Dijkstra 就行，但地铁场景有一个特殊约束：换乘是有额外时间的。从一个公司的线路换到另一个公司的线路，中间要步行、等车，这部分时间不能简单算成一条边。

怎么建模？一个常见的做法是把每个站拆成多个状态节点，比如"在这个站属于线路 A"和"在这个站属于线路 B"是两个不同的节点。站内换乘就变成从线路 A 的节点到线路 B 的节点的一条边，权重是换乘时间。这样建出来的图还是普通的带权图，照样能用 Dijkstra 求解。

这个例子想说明的是：很多实际问题，难点不在于算法本身，而在于怎么把场景抽象成图。抽象对了，最后跑的算法往往就是最基础的那几个。我整理这些细节的时候反复强调"先建图再选算法"，原因也在这里。

至少在我接触过的项目里，图的算法并不复杂，复杂的是识别出"这是个图论问题"并把规则翻译成边权。把那一步做对了，剩下的就是按部就班地写模板代码。