目录
1. 图中计算复杂度简介
在计算机科学中，评判算法很少仅仅看它们是否产生正确的结果。更是根据它们产生该结果的效率来评判。随着数据规模的扩大——无论是分析拥有数十亿用户的社交网络，还是计算全球航运路线的物流——效率成为了最终的瓶颈。
我们使用Big O表示法 (大O符号)来衡量效率，它提供了算法所需的时间（执行速度）和空间（内存消耗）的上限，这取决于输入的大小。在图论中，输入大小几乎总是由两个参数定义：
V(或|V|): 图中顶点（Vertices）（节点）的数量。E(或|E|): 图中边（Edges）（连接）的数量。
图可以是稀疏的（Sparse）（其中E接近V）或密集的（Dense）（其中E接近V²）。图的稀疏性或密集性很大程度上决定了哪些算法——以及哪些数据结构——会表现最佳。
经验法则： 如果一个算法在 O(V²) 时间内运行，它可能对一个具有 1,000 个顶点的图（1,000,000 次操作）是可以接受的。但是对于一个具有 1,000,000 个顶点的图，它需要 1,000,000,000,000 次操作，这使其对于实时应用完全无效。理解渐近复杂度是系统设计中不可妥协的必修课。
2. 图的表示：无声的复杂度修改器
在分析任何特定算法之前，我们必须讨论图的表示法。在内存中存储图的方式会从根本上改变对其执行的每个操作的时间和空间复杂度。最常见的两种表示法是邻接矩阵 (Adjacency Matrix)和邻接表 (Adjacency List)。
邻接矩阵
邻接矩阵是一个大小为 V × V 的二维数组。索引为 matrix[i][j] 的单元格包含一个布尔值（或权重），指示是否存在从顶点 i 到顶点 j 的边。
- 空间复杂度：
O(V²)。这是极其消耗内存的。对于一个包含 100,000 个节点的图，该矩阵需要 100 亿个条目。 - 边查找（i和j是否连接？）：
O(1)。即时验证。 - 查找顶点的所有邻居：
O(V)。您必须遍历该顶点的整行，检查所有可能的连接，即使该图是稀疏的。
邻接表
邻接表是一个列表数组（或哈希映射）。索引代表顶点，该索引处的列表包含其所有连接的邻居。
- 空间复杂度：
O(V + E)。这是最优的，因为它只存储顶点和实际存在的边。 - 边查找：
O(deg(V))，其中deg(V)是顶点的度数（邻居数）。在最坏情况下（密集图），这是O(V)，但在稀疏图中，它实际上是O(1)。 - 查找顶点的所有邻居：
O(deg(V))。您只需遍历实际存在的邻居，使得遍历速度极快。
结论： 除非处理的是需要常量时间边界查找的密集图，否则邻接表是标准的。在本文的其余部分，除非另有说明，请假设所有复杂度均基于邻接表表示法。
3. 图遍历算法
遍历构成了几乎所有复杂图逻辑的主干。它们被用来系统地访问图中的每一个节点和每一条边。
广度优先搜索 (BFS - Breadth-First Search)
BFS 逐层探索图，从源节点开始，探索其所有直接邻居，然后再进入下一层。它使用队列（FIFO）数据结构。
- 时间复杂度：
O(V + E)。每个顶点恰好入队和出队一次O(V)，并且每条边对于有向图被检查一次或对于无向图被检查两次O(E)。因此，总操作数随图的大小线性增长。 - 空间复杂度：
O(V)。在最坏情况下（如星型图），队列将同时保存除根之外的所有顶点。访问数组也需要O(V)空间。 - 用例： 无权图中的最短路径、点对点网络、网络爬虫。
深度优先搜索 (DFS - Depth-First Search)
DFS 沿着分支尽可能深地探索，然后再回溯。它严重依赖于递归（调用栈）或显式栈（LIFO）。
- 时间复杂度：
O(V + E)。与 BFS 类似，每个顶点被访问一次，并且每条边被检查一次（或两次）。渐近时间与 BFS 相同。 - 空间复杂度：
O(V)。如果图是一个长的单路径（例如，链表结构），递归栈的最大深度可以达到V。 - 用例： 拓扑排序、循环检测、解决迷宫、高度约束环境中的路径查找。
4. 最短路径算法
最短路径算法是现实世界中最常使用的图算法，广泛应用于地图服务、网络路由协议和AI导航。
Dijkstra 算法
Dijkstra 算法计算从单一源节点到具有非负边权的图中所有其他节点的最短路径。它采用贪心（Greedy）方法和优先队列（Priority Queue）。
Dijkstra 的复杂度完全取决于用于实现优先队列的数据结构。
- 使用基础数组/列表： 时间：
O(V²)。提取最小值需要O(V)，执行V次。更新邻居共需O(E)。最适合E ≈ V²的密集图。 - 使用二叉最小堆： 时间：
O((V + E) log V)。提取最小值需要O(log V)，执行V次。更新键值 (decrease-key) 需要O(log V)，执行E次。最适合典型的稀疏图。 - 使用斐波那契堆： 时间：
O(E + V log V)。斐波那契堆允许在O(1)的摊销时间内运行decrease-key操作，只留下V次提取操作需要O(log V)。这是 Dijkstra 的理论最优复杂度。 - 空间复杂度：
O(V)。用于存储距离、前驱和优先队列。
Bellman-Ford 算法
与 Dijkstra 不同，Bellman-Ford 可以处理包含负权边的图并检测负权环。它通过反复“松弛”所有边来实现这一点。
- 时间复杂度：
O(V × E)。算法循环V-1次，在每次循环中，它遍历所有的E条边。这比 Dijkstra 慢得多，因此它只应在存在负权边时使用。 - 空间复杂度：
O(V)。需要一个数组来存储当前距源的最小距离。
Floyd-Warshall 算法
Floyd-Warshall 是一种全源最短路径算法。它能找出加权图中所有顶点对之间的最短路径（即使存在负权边，只要没有负权环）。它使用动态规划（Dynamic Programming）。
- 时间复杂度：
O(V³)。它具有三个嵌套循环，每个循环从 1 迭代到V，以更新最短路径矩阵。由于这种三次方的复杂度，它只适用于小型图（通常V < 500）。 - 空间复杂度：
O(V²)。它维护一个二维距离矩阵。
A* 搜索算法
A* 是一种目标导向的搜索算法，广泛用于电子游戏寻路（如 NPC 移动）和 GPS 路由。它本质上是 Dijkstra 算法的扩展，增加了一个启发式函数（Heuristic function） h(n)，用于估计到目标的距离，从而引导搜索方向。
- 时间复杂度： 最坏情况下为
O(b^d)，其中b是分支因子（每个节点的平均边数），d是最优解的深度。在最佳情况下（完美的启发式），它是O(d)。如果启发式函数为 0，A* 退化为 Dijkstra 的O((V + E) log V)。 - 空间复杂度： 最坏情况下为
O(b^d)，因为它必须将所有生成的节点保留在内存中（在 OPEN 和 CLOSED 列表中）。巨大的空间需求通常是 A* 的瓶颈，导致了像迭代加深 A*（IDA*）这样的变体。
5. 最小生成树算法
最小生成树 (Minimum Spanning Tree, MST) 是连通的、带边权的无向图的边的一个子集，该子集将所有顶点连接在一起，不包含任何循环，且总边权尽可能小。MST 在网络设计中至关重要，例如铺设电缆、电网和管道系统。
Kruskal 算法
Kruskal 采用全局贪心方法：按权重对所有边进行排序，然后不断选取不会形成环的最小边。它依赖于并查集（Disjoint-Set / Union-Find）数据结构来检测循环。
- 时间复杂度：
O(E log E)或O(E log V)。对边进行排序占主导地位，需要O(E log E)。因为E ≤ V²，log E ≤ 2 log V，这意味着O(E log E)渐近等价于O(E log V)。并查集操作实际上只需要O(1)的时间，具体来说是O(α(V))，其中α是反阿克曼函数。 - 空间复杂度：
O(V + E)，用于存储图和并查集结构。
Prim 算法
Prim 算法一步一步地构建 MST，从一个任意节点开始，贪心地添加将生长中的树连接到树外新顶点的最廉价的边。
- 时间复杂度： Prim 的复杂度取决于使用的优先队列，这使其分析与 Dijkstra 算法完全相同。使用二叉堆时，运行时间为
O((V + E) log V)。使用斐波那契堆时，运行时间为O(E + V log V)。 - 空间复杂度：
O(V)，用于优先队列和跟踪数组。
Kruskal 对比 Prim： 通常，Kruskal 算法首选用于稀疏图（因为对 E 个元素排序很快），而使用斐波那契堆的 Prim 算法在数学上对于密集图来说更优越。
6. 连通性与拓扑排序
分析图中的结构和依赖关系需要专门的算法。它们主要在有向无环图 (DAG) 和复杂的有向网络上运行。
拓扑排序 (Kahn算法 & 基于DFS)
拓扑排序是其顶点的一种线性排序，使得对于每条从顶点 u 到顶点 v 的有向边 uv，u 都排在 v 之前。它主要用于任务调度、解决包依赖关系和构建系统。
- 时间复杂度：
O(V + E)。Kahn算法（使用入度数组和队列）和基于DFS的方法都精确访问每个节点和边各一次。 - 空间复杂度：
O(V)，用于队列/栈和记录访问状态及入度的数组。
强连通分量 (Tarjan 和 Kosaraju)
有向图中的强连通分量 (Strongly Connected Component, SCC) 是最大的顶点子集，在该子集内，每个顶点都可从任何其他顶点到达。识别 SCC 在推荐引擎、电路设计和生态系统建模中至关重要。
- Kosaraju 算法： 涉及两次 DFS 遍历。第一次遍历原图，第二次遍历转置图（反向边）。时间：
O(V + E)。空间：O(V)。 - Tarjan 算法： 只需要一次 DFS 遍历，使用数组跟踪“low link”值以识别分量根。时间：
O(V + E)。空间：O(V)。在实践中通常更倾向于使用 Tarjan 算法，因为只执行一次 DFS 具有更好的缓存局部性，且不需要反转整个图。
7. 网络流算法
网络流算法确定可以通过定义了容量的管道网络从源点流向汇点的最大流。其应用包括流量路由、流体动力学、二分图匹配和互联网数据包路由。
Ford-Fulkerson 方法
最初的方法是使用 DFS 从源点到汇点寻找增广路径，并推送流量，直到没有路径剩余。
- 时间复杂度：
O(E × F)，其中F是网络的最大流。危险在于，如果容量非常大或是无理数，Ford-Fulkerson 可能需要极长的时间，甚至永远无法终止。这是伪多项式时间。 - 空间复杂度：
O(V)，在 DFS 期间维护已访问数组。
Edmonds-Karp 算法
Ford-Fulkerson 的一种实现，它使用 BFS 而不是 DFS 来寻找最短增广路径（就边数而言）。这保证了算法能够终止。
- 时间复杂度：
O(V × E²)。可以证明最大增广次数受O(V × E)限制，并且每次 BFS 需要O(E)。这是强多项式时间，且独立于最大流F。 - 空间复杂度：
O(V + E)，用于 BFS 队列和存储残余图。
Dinic 算法
Dinic 算法通过使用 BFS 构建“分层图 (Level Graphs)”，然后使用 DFS 寻找阻塞流同时推送多个流，从而极大地优化了流的计算。
- 时间复杂度：
O(V² × E)。在单位容量网络（如二分图匹配）中，复杂度显著降至O(E × √V)。它是竞赛编程和实际网络流执行的黄金标准。 - 空间复杂度：
O(V + E)。
8. NP困难图问题
图论中一些最著名的问题没有任何已知的多项式时间 O(N^k) 解法。它们被归类为 NP-Hard，意味着它们的复杂度呈阶乘或指数级增长。
旅行商问题 (TSP)
寻找访问每个节点恰好一次并返回起点的可能的最短路线。
- 暴力破解：
O(V!)（阶乘时间）。评估所有排列。当V > 15时无法使用。 - 动态规划 (Held-Karp)：
O(V² 2^V)。比阶乘时间好很多，但仍然是指数级的。空间复杂度非常高：O(V 2^V)。当V > 30时无法使用。
图着色问题
为每个顶点分配一种颜色，使得没有两个相邻的顶点具有相同的颜色，同时使用最少数量的颜色。
- 时间复杂度： 检查一个图是否可以用
k种颜色着色是 NP完全问题。精确算法的运行时间为O(2^V)或更糟。现代解决方案依赖于启发式算法、贪心方法（如 Welsh-Powell）或近似算法，而不是寻求完美的解决方案。
9. 终极复杂度备忘录
收藏此页面。下面是一个全面的表格，总结了讨论的每个算法的时间和空间复杂度。（假设使用邻接表表示法并在适用的情况下使用二叉堆）。
| 算法 | 类别 | 时间复杂度 (最坏) | 空间复杂度 |
|---|---|---|---|
| 广度优先搜索 (BFS) | 遍历 | O(V + E) |
O(V) |
| 深度优先搜索 (DFS) | 遍历 | O(V + E) |
O(V) |
| Dijkstra (二叉堆) | 最短路径 | O((V + E) log V) |
O(V) |
| Dijkstra (斐波那契堆) | 最短路径 | O(E + V log V) |
O(V) |
| Bellman-Ford | 最短路径 (负权) | O(V × E) |
O(V) |
| Floyd-Warshall | 全源最短路径 | O(V³) |
O(V²) |
| A* 搜索 | 启发式搜索 | O(b^d) |
O(b^d) |
| Kruskal 算法 | 最小生成树 | O(E log E) |
O(V + E) |
| Prim 算法 | 最小生成树 | O((V + E) log V) |
O(V) |
| 拓扑排序 | DAG 处理 | O(V + E) |
O(V) |
| Tarjan / Kosaraju | 强连通分量 | O(V + E) |
O(V) |
| Ford-Fulkerson | 网络流 | O(E × F) |
O(V) |
| Edmonds-Karp | 网络流 | O(V × E²) |
O(V + E) |
| Dinic 算法 | 网络流 | O(V² × E) |
O(V + E) |
| 旅行商问题 (DP) | NP困难 | O(V² 2^V) |
O(V 2^V) |
常见问题解答 (FAQ)
为什么图的表示对复杂度很重要？
邻接矩阵和邻接表之间的选择会极大地改变算法的时间和空间复杂度。邻接表通常在稀疏图中表现更好，而邻接矩阵更适合密集图和快速查找边的情况。
Dijkstra算法的时间复杂度是多少？
使用二叉堆，Dijkstra算法的运行时间为 O((V + E) log V)。如果使用优化的斐波那契堆，时间复杂度会降至 O(E + V log V)，使其在密集图中运算更快。
BFS和DFS在复杂度上有什么区别？
广度优先搜索（BFS）和深度优先搜索（DFS）在最坏情况下的时间复杂度相同，均为 O(V + E)，且在邻接表表示法下空间复杂度均为 O(V)。它们的区别在于遍历模式和结构应用，而非渐近复杂度。
资源与进一步探索
-
维基百科：时间复杂度
全面概述算法复杂度理论，包括大O表示法 (Big O Notation)。
-
MIT OpenCourseWare 视频课程：算法导论
经典的麻省理工学院 (MIT) 课程，提供图和其他数据结构极度深入的数学复杂度分析。
-
《算法导论》 (Cormen, Leiserson, Rivest, Stein)
常被称为“CLRS”，这是全球算法领域的圣经。对于正式掌握复杂度是不可或缺的。