Skip to content

图

基础知识

图（graph）由点（vertex）和边（edge）组成，点一般表示某个对象，边表示两个对象之间的关系。通常用 表示顶点和边的集合，图记为 。

从边的类型分析，图可以分成两类：无向图（undirected）和有向图（directed）。无向图的边是无序对 ，其中 称为端点（endpoint），边 和 没有区别。有向图的边是有序对 ，边从 （尾部（tail））到 （头部（head））。如下图所示。

对于一个图 做计算，输入规模用点的个数和边的个数表示。一般表示为 。

如果一个图是连通的、无平行边的无向图，有 个顶点，那么最少有 个边，比如线性图、星状图、树状图等等，最多有 个边，也就是任意两个顶点之间都有一条边，这样的图称为完全图（complete graph）。

如果 是一个无向图，顶点 的度（degree）是指 中与 关联的边的数量，也就是以 为端点的边的数量。

根据边的多少，可以分为稀疏图（sparse）和稠密图（dense）。不同的数据结构和算法可能会更适合某种类型的图。边最少的时候 ，边最多的时候 。一般接近线性称为稀疏图，比如 ，接近平方称为稠密图，比如 。 条边可以认定为部分稠密，具体要结合应用场景，可以被视为稀疏图，也可以被视为稠密图。

图的表示

最常用的图表示有两种：邻接链表（adjacency list）和邻接矩阵（adjacency matrix）。

邻接链表的组成要素有

  • 一个包含图中所有顶点的数组。
  • 一个包含图中所有边的数组。
  • 对于每一条边，指向其两个端点的指针。
  • 对于每一个顶点，指向其每一条关联边的指针。

每个图由两个数组，两个数组之间相互引用。对于有向图，每个顶点 包含两个指针数组，一个是出边（ 是尾部），一个是入边（ 是头部）。

如果有 个顶点， 条边，那么这四个要素的空间占用分别是 ，因此邻接链表表示图的空间复杂度是 。

邻接矩阵使用一个 的矩阵表示，其中 因此，邻接矩阵的空间复杂度是 。

通过修改 可以表示不同的图。比如有平行边的情况下， 表示点 之间边的个数。对于带权图，可以令 。

对于无向图而言，邻接矩阵是对称矩阵。

使用哪种表示取决于场景。邻接矩阵适合表示稠密图，对于稀疏图就会浪费空间。另外，还需要考虑想要支持的操作。通常情况下，邻接链表表示更合适一些。

广度优先搜索

广度优先搜索（Breadth-First Search, BFS）算法相当直接、简洁。

从图 的某点 开始遍历，假定它是第 0 层。首先遍历它的邻接边；如果边所指向的顶点尚未被访问，则该顶点位于第 1 层。然后遍历第 1 层的点，遍历它们的邻接边，如果边所指向的顶点尚未被访问，则该顶点位于第 2 层。以此类推。伪代码如下所示。 

marked[s] = true; // other false
queue = {s};
while !queue.IsEmpty()
    v = queue.pop()
    for Edge(v, w) in v.AdjacencyEdge()
        if !marked[w]
            marked[w] = true
            queue.push(w)
如果点 被标记了，当且仅当从 到 存在一条通路。

BFS 算法的时间复杂度是 ，其中 。除了初始化 marked 之外，其他部分的时间复杂度是 ，角标 表示从 可达的边和点的数量。每个点进入 queue 一次，因此 while、pop、push 和 marked[w] = true 这几句的复杂度是 ；每条边最多会遍历两次，一次是 v 被标记的时候，一次是 w 被标记的时候，因此复杂度是 ，因此总的时间复杂度是 。

实现参考 BFS

深度优先搜索

深度优先搜索（Depth-First Search, DFS）和 BFS 有相似之处，都是遍历图的一种方式、一种策略，不过这种策略略微不同。

从 点开始，遍历所有的邻接边，遇到第一个没有访问过的顶点 ，访问点 ，然后遍历 的所有邻接边，遇到第一个没有访问过的顶点 ，访问点 ，然后遍历 的所有邻接边，以此类推。直到遇到一个顶点，其所有邻接边所指向的顶点都访问过了，然后返回上一层。

直接将上述过程翻译成代码，和 BFS 的先入先出不同，这里是后入先出，需要使用数据结构 stack 来保存中间的顶点。和 BFS 另一个区别是标记访问的时机略微有差异。下面是伪代码。 

marked[0..V] = false;
stack = {s}
while !stack.IsEmpty()
    v = stack.pop()
    if !marked[v]
        marked[v] = true
        for Edge(v, w) in v.AdjacencyEdge()
            stack.push(w)

使用了栈，那么一个更优雅的实现是递归。 

marked[s] = true;
for Edge(s, w) in s.AdjacencyEdge()
    if !marked[w]
        DFS(G, w)

和 BFS 类似，点 被标记了，当且仅当从 到 存在一条通路。

时间复杂度也和 BFS 一样，。每个边最多访问两次，初始化复杂度和点的个数成正比。

实现参考 DFS

寻找路径

利用 BFS 可以找到一条从 到 的路径（path）。对于无权图，BFS 找到的路径是最短路径。时间复杂度和 BFS 一致，为 ，其中 是从 可达的边和顶点的个数。

实现参考 Path

这个问题也可以用 DFS 解决，不过此时只能找到一条通路，并不是最短路径。

连通分量

一个无向图 ，连通分量（connected component）是最大的子集 ，其中 内的任意两个顶点是连通的。

利用 BFS 可以找到图的各个连通分量。只需要最外面遍历所有的点，如果该点没有被访问过，那么从该点出发，应用 BFS 遍历所有能达到的点，这些点属于同一个连通分量。

如果给每一个连通分量一个 id，那么 id 相同的点属于同一个连通分量，反之，同一个连通分量中的点，id 相同。

从顶点 开始的 BFS 的时间复杂度是 ，其中 表示该连通分量中边和点的个数。每一个连通分量只会调用一次 BFS，也就是说， 中的每一个顶点和每条边都只属于一个连通分量，将这些 BFS 的运行时间相加，恰好就是 。一些初始化工作的复杂度是 。因此最终时间复杂度是 。

实现参考 ConnectedComponent

这个问题也可以用 DFS 解决。

拓扑排序

一些任务，存在优先级约束（precedence constraint），在某个任务完成之前，无法开始另一个任务。比如大学中的课程有前置课程。拓扑排序就是来解决这类问题的。

拓扑序（topological ordering）的定义是对于给定的有向图 ，为每个顶点 分配 中唯一的一个值 ，使得对于每一条边 都有 。

每一个图都有拓扑序吗？答案显然是否定的。如果一个有向图包含环，那么无法进行拓扑排序，如果一个有向图不包含环，那么称为有向无环图（directed acyclic graph, DAG）。

每个有向无环图至少有一个源顶点（source vertex），该点没有入边。从任一点开始，沿着入边逆向，总会找到源顶点，否则的话，会找到一个环，而这与有向无环图定义矛盾。

每一个有向无环图至少有一个拓扑序。令 是一个有 个顶点的图，拓扑排序就是将 分配给各个点。假定 是 的源顶点，那么给它分配 1，即 。如果有多个源顶点，任选一个即可。将 中的 及其所有出边删除，得到 ，由于 是有向无环图， 也是。因此， 存在一个源顶点，可以将剩余的数 中的 2 分配给它。递归进行，直到所有点都被分配一个数。在 中而不在 中的边只有 的出边，而 ，因此满足拓扑排序的要求。

利用 DFS 可以高效地实现拓扑排序。在 DFS 之外遍历所有顶点，如果顶点没有被访问过，就调用 DFS 从该顶点开始遍历。在准备退出 DFS 时，给顶点分配一个值。该值初始为 ，每分配一次，执行 label--。

实现参考 Topology

拓扑排序每个顶点只会访问一次，每个边也只会访问一次，因此算法的时间复杂度是 。

对于每一个顶点 ，只访问了一次，在结束访问的时候分配一个值，然后对 label 自减，因此分配的每个值都不一样。

对于边 ，要保证 。这里有两种情况需要讨论。第一种情况是先访问 ，然后递归 DFS 访问 。由于是先进后出，那么先结束对 的访问再结束对 的访问，因此先给 分配再给 分配。由于 label 是递减的，因此 。第二种情况是先访问 ，对于有向无环图，那么没有通路从 到 ，否则会形成一个环。在这次 DFS 递归结束前不会访问 也就不会给 分配一个值，但是在结束前会给 分配值，因此 。

强连通分量

一个有向图 ，强连通分量（strongly connected component）是最大的子集 ，其中 内的任意一个顶点都有一条通路能到任意其他顶点。虽然定义和无向图的连通分量类似，但是实际含义完全不同。比如下面的图，看似是连通的，但并不是强连通分量，因为除了 1 之外其他点不能到任意点。

下图有四个强连通分量，每个连通分量都有环。

如果将第二个图中的强连通分量都看做一个顶点，那么和第一个图一样是一个有向无环图。准确的描述如下。

令 是一个有向图，那么可以定义一个元图（meta-graph），元顶点（meta-vertex） 对应 的一个强连通分量，如果 中存在一条边，从 对应的强连通分量中的某个顶点指向 对应的强连通分量中的某个顶点，就有一条元边（meta-edge）。 是有向无环图。假定 中有 个顶点构成一个有向环，那么这个环会使得 中的强连通分量 合并为一个强连通分量，因为可以从 中的任一点沿着环到达其他强连通分量。

上述论证使得我们可以将有向图分成两层：图的高层结构是由强连通分量组成的有向无环图；每一个强连通分量则是更细粒度的结构。

上图如果从顶点 6 开始遍历，不管是 DFS 还是 BFS，都会找到一个强连通分量，如图中所示的 SCC#4。但是如果从 1 开始遍历，就无法得到一个强连通分量。如果能从合适的地方开始，就能找到一个强连通分量。如果一个强连通分量是一个汇点（sink），即没有出边，那么从该强连通分量的任一点开始遍历，恰好能得到该强连通分量；然后将其去掉，再继续寻找其他连通分量。在对应的元图中，汇点是拓扑序的最后一个顶点，因此应按拓扑序的逆序处理各个强连通分量。关键问题是如何找到这些汇点。

令 是有向图。对 进行 DFS，并在顶点完成访问时按 的顺序为其编号，记该编号为 。令 是两个强连通分量，并且 有一条边 ，其中 ，那么 证明过程和拓扑排序类似。考虑两种情况。第一种情况是 DFS 先访问 中的点 ，那么存在通路 ，其中 。编号按完成访问的逆序分配；又因为 DFS 先入后出，所以 中各点的编号小于 中各点的编号。第二种情况是先访问 中的点 。因为 的元图是有向无环图， 没有到 的通路，因此 完成访问时仍不会访问 中的任意一点。这种情况下， 中各点的编号也小于 中各点的编号。

元图逆后序中的第一个顶点所在的强连通分量是源节点（source），只有出边没有入边，和汇点相反。

如果我们将整个图转置，边的方向取反，会发生什么呢？两个图的强连通分量一致，并且源节点变成汇点，汇点变成源节点。对转置图进行 DFS，按顶点完成访问的逆序处理顶点时，第一个顶点所在的强连通分量就是原图的汇点。

通过上述的讨论，我们推导了 Kosaraju 算法最核心的思想。算法的伪代码如下。 

G_rev = G.Reverse()
marked_rev[1..n] = false
t = Topology(G_rev)
marked[1..n] = false
numSCC = 0
for v in t.order()
    if !marked[v]
        numSCC++;
        DFS(G, v)

DFS(Graph, s)
    marked[s] = true
    scc[s] = numSCC
    for (s, v) in s.AdjacencyEdge()
        if !marked[v]
            DFS(Graph, v)

上述实现使用了两次 DFS，每个顶点和每条边都会访问两次，额外有一些常量开销或者和顶点数成比例的开销，因此算法的时间复杂度是 。

根据上述讨论，每次调用 DFS 会发现一个新的强连通分量，这个强连通分量是未访问顶点所组成子图的汇点。因此如果 属于同一个强连通分量，那么 。

实现参考 ConnectedComponent

最短路径

Dijkstra 算法

Dijkstra 算法主要用于解决最短路径问题（shortest path problem）。给定一个有向图 ，从一个顶点 开始，每条边 的长度是非负的，算法的输出是对任一点 的 。如果两个点 之间没有通路，那么 是无穷大。

这里有两个假设：图是有向图，且边的长度非负。

Dijkstra 算法的伪码如下。 

X = {s}
len[s] = 0; len[v] = MAX for v != s
while exists(v, w), v in X, w not in X
    (v_min, w_min) = minimizing len[v] + len(v, w)
    X.add(w_min)
    len[w_min] = len[v_min] + len(v_min, w_min)
集合 X 初始时仅包含 s 这一个点。s 到 s 的距离为零，其他点的距离初始化为最大值，这些距离保存在 len 数组中。每一次迭代向集合 X 中添加一个顶点。迭代要考察所有从 X 到 V-X 的边。这里定义 Dijkstra 得分 len[v] + len(v, w)，即 s 到 v 的距离加上 的长度。假定边 使得分最小，那么将 w_min 加到 X 中，然后更新 len[w_min]。

直观的看，整个算法将点分成已经计算出最小距离的点和等待计算的点。每一次找一个局部最优的点，更新其最小距离，然后加到已经处理的集合中。

前面假定距离必须是非负数，是否可以通过把所有边都加上绝对值最大的负数的绝对值，这样所有的边都是非负数，然后再用 Dijkstra 算法解决呢？答案是否定的。本质原因在于这样不同长度的路径加上了不同的值，长的路径惩罚更大，导致规约后的问题与原始问题不等价。

如果直接处理包含负权边的问题呢？下图是一个简单的情况。第一次迭代时，明显 小于 ，因此会将到点 的最小距离标记为 ；但最短距离实际上应为 。

这里使用 来表示 到 的最短距离，那么需要证明对所有的 都有 ，后者是 Dijkstra 算法给出的最短距离。

使用数学归纳法证明。 表示 Dijkstra 算法正确的计算了 到第 个加到了集合 中的顶点的最短距离。当 时， 到 的距离是 0，len[s] 初始化为零，显然成立。

假设 都成立。令 表示第 个加到 的顶点，令 是选中的边，根据算法 已经在 中了。算法得到的 ，为了证明这个值等于 ，下面分两种情况讨论。

首先证明 。根据假设， 已经在 中了，并且 。假定有一条从 到 的路径 ，距离是 ，算法计算的路径长度是 ，如下图所示，我们称这条路径为 。显然，真实的最短路径 不能比 更长，因此 最多和 一样。

接着证明 ，也就是要证明上图中 的距离至少是 。假定 的最短路径是 。我们对 知之甚少，不过知道 属于 而 不属于 ，那么一定有一条跨越边界的边，不妨令第一条这样的边是 。如下图所示。那么 可以分成三段，第一段是 到 ，根据归纳法假设，这段最短距离是 ；第二段是 到 ，距离是 ；第三段是 到 ，这一段的距离非负。因此 由于 ，那么 而右边恰好是 Dijkstra 算法最小化的得分。也就是说，选择的 满足 ，那么 因此路径 至少和 一样大。

结合两个部分，完成了证明。还有一种情况，就是 永远不会加到 里面，即 到 没有通路，那么保持 。

上述算法并没有描述如何找到最小的边 。一个直观的方式是使用一个 bool 表示点是否属于 。然后每次迭代，都要遍历所有的边，首先判断其是否跨越边界，即边的起点在 中、终点不在 中。如果跨越边界，计算 Dijkstra 得分 len[v] + len(v, w)，选择得分最小的边，然后把终点 w 加到 中。需要迭代 次，每次迭代需要遍历所有的边 ，因此时间复杂度是 。

这个复杂度有点高，当边和点数很多时就会力不从心。我们需要借助堆来提升得到最小值的速度。

下面首先介绍使用堆最核心的思想，然后介绍一些可能的工程实现。

堆里面放的是待处理的顶点和当前到该点最短距离，即 当将 从 移动到 的时候，需要更新与 邻接的点 对应的距离。

下面是伪代码。 

key[s] = 0, key[v] = MAX for v != s
H = Heapify(key)
while !H.empty()
    w_min = H.Top()
    H.Pop()
    len[w_min] = key[w_min]
    // update key
    for Edge(w_min, v) in w_min.AdjacencyEdge()
        if H.Contains(v) and len[w_min]+l_{w_minv} < key[v]
            key[v] = len[w_min]+l_{w_minv}
            H.Update(v, key[v])
和之前的伪代码相比，这里由 H 跟踪尚未处理的点，而不是显式维护集合 X，目的都是区分一个点是否已被处理。

H 的大小和顶点个数 一致，因此 w_min = H.Top() 和 H.Update(v, key[v]) 的时间复杂度是 ，前者外层的 while 循环次数是点的个数 ，后者外面两层循环，但万变不离其宗，最多遍历了边两次，那么循环次数是 ，因此优化版本的时间复杂度是 ，比上述最朴素的版本 快相当多，特别是点和边数量很大的情况。

堆里面放的是待处理的数据这一点是确定的，但是如何放是可以选择的，一种常见方法就是将所有顶点都放到堆里面，起点的距离是 0，其余点的距离是最大值，即上面的伪代码阐述的方式。另一种方式是堆里面只放已经被发现但是还没有被处理的顶点。初始的时候只放起点，然后再处理邻接点的时候（发现）再放进堆。

如果使用普通的堆来实现，有两个问题。第一个问题是需要将顶点和距离封装成一个结构体或者 std::pair，并自定义比较运算符。第二个问题是不能删除或更新指定的节点，因此算法中的更新操作只能再次添加一个节点，即重复入堆。如果弹出的顶点已经处理过，即已经在 中，无需再次处理，这个过程也称为懒删除。重复入堆的次数至多与边数同阶，堆操作的时间复杂度从 变成了 。对于简单图， 最多是 ，因此渐近时间复杂度不变，不过系数最多可能会变大一倍。

也可以使用带有 Index 的堆来实现，这种数据结构一般称为 IndexPriorityQueue。对于普通堆的第一个问题，顶点的 id 就是天然的 Index，那么堆里面放最小距离即可。第二个问题就不存在了，因为其支持更新操作。

代码示例中，选择了 IndexPriorityQueue 和动态添加待处理的点。参考 Dijkstra

Bellman-Ford 算法

前面分析过，Dijkstra 算法不能处理负权边。现在来分析边的权重可能为负数的情况。当所有边的权重都为正数时，即使存在环，也可以自然处理。沿环回到起点时，距离只会变大，不会变小，因此不会影响最短路径的计算。负权边的情况则不同。如果存在负权环，沿环回到起点时距离会变小，不断绕行，距离会趋向负无穷大，因此最短路径没有定义。因此需要假设图中不存在负权环。

Bellman-Ford 算法是动态规划算法，因此最关键的步骤是找到如何从子问题来构建最优解，即分析解的结构特征。

Bellman-Ford 算法从输出的角度设计算法。直观地看，最短路径 的一个前缀 是到另一个点的最短路径。如果这一点成立，那么 就是更小的问题。由于存在负权重的边， 的长度可能小于 的长度，所以两者的长度关系不确定。不过可以确定的是， 的边数一定小于 的边数。因此我们使用跳数 来定义子问题。令 表示从 到 的最短路径，且该路径的边数不超过 。路径上可以有环，如果多次使用同一条边，会增加跳数的计数。由于不存在负权环，这里的环只会增加距离。

从顶点 出发，最短路径的边数最多是 ，因此 不会大于 ，那么子问题 有 个。假定某个最短路径有 个边，那么有 个顶点，那么某个 必然会重复出现，形成一个环。由于不存在负权环，那么去掉这个环，得到的路径距离不会变大，因此可以得到一个边数更小权重不变或变小的路径。因此最短路径的边数不会超过 。

选取子问题之后，接下来分析如何从子问题构建最优解。假定 是从 到 的最短路径，且该路径的边数不超过 。如果 的边数小于 ，那么 。如果 的边数等于 ，假定最后一条边是 ，那么前缀路径 是从 到 的最短路径，且其边数不超过 ，因此 。用反证法证明 是从 到 的最短路径。如果不是，那么存在一条更短的路径 从 到 ，即 ，那么 就是从 到 的更短路径，这与 是最短路径矛盾。结合上述两种情况，我们可以得到 如果从 到 没有不超过 条边的路径，那么 。

从上式可以看出， 只依赖于 和 。如果对所有的 均有 ，算法就可以终止。此时对于任意 ，都有 ，并且 是最短路径。用反证法证明。假定 不是最短路径，那么存在一条跳数 的路径 ，其距离小于 ，但这与前面的结论 矛盾。

一定会有这么一个 吗？前面分析过，最短路径的边数不会超过 ，因此最坏情况就是 ，此时 。

算法的伪代码如下。 

predecessor[0..n-1] = nullptr
L[0..n,0..n-1]
L[0][s] = 0, L[0][v] = MAX for v != s
for i = 1 to n
    stable = true
    for v in V
        w_min = min_{(w,v)\in E}(L[i-1][w]+l_{wv})
        if w_min < L[i-1][v]
            predecessor[v] = w
            L[i][v] = w_min
        else
            L[i][v] = L[i-1][v]

        if L[i][v] != L[i-1][v]
            stable = false
    if stable
        return L[i-1][v] for all v in V

return N/A // there is a negative weight cycle
内层 for 循环迭代 次，里面要遍历与 相邻的边，整体要遍历所有的边 ，因此内层循环的时间复杂度是 。外层 for 循环遍历 次，因此总的时间复杂度是 。这里记录了每次更新后点 的前继节点，因此可以在算法结束后沿着前继节点回溯，得到从 到 的最短路径。数组 predecessor 的大小是 ，因此回溯的时间复杂度是 。

实现参考 Bellman-Ford。

Floyd-Warshall 算法

上面的 Dijkstra 和 Bellman-Ford 算法都是从一个顶点出发，计算从该顶点到其他所有顶点的最短路径。如果需要计算所有顶点对之间的最短路径，那么需要对每一个顶点都运行一次 Dijkstra 或 Bellman-Ford 算法，时间复杂度是 或 。这里介绍一个更高效的算法：Floyd-Warshall 算法。

Floyd-Warshall 算法的子问题构造也相当精妙。给定一个起始点 和终点 ，以及一个整数 ，令 表示从 到 的最短路径长度，且该路径上所有的中间顶点都在 中，这里的中间顶点是指除了起始点和终点之外的顶点。同时，路径不包含有向环。 的取值范围是 ，因此子问题的个数是 。当 时，路径上没有中间顶点。若 ，则零长度路径的长度为 ；若 ，则一条边构成的路径长度为 ；否则路径长度为 。

假定 是从 到 的最短路径，没有环，且所有的内部点都在 中。最短路径的构成分为两种情况。第一种情况是 的内部点不包含顶点 ，那么 的所有内部点都在 中， 必须也是这个子问题的最短路径，任何更优的解都是原始问题（）的更优解，这与假设矛盾，因此 。第二种情况是 的内部点包含顶点 ，那么 可以分成两段： 是从 到 的最短路径，且所有的内部点都在 中； 是从 到 的最短路径，且所有的内部点都在 中。由于 没有环，顶点 只会出现一次，因此可以做出这样的划分。反证法可以证明，如果 或 不是最短路径，那么就会存在更短的路径 或 ，使得 或 成为从 到 的更短路径，这与假设矛盾。因此 。

上述第二种情况的讨论有一个瑕疵， 或 与 或 组成的新路径可能包含环。可以剪掉其中的环，得到路径 。假定图不包含负权环，那么 的长度不大于原路径的长度，从而仍然是更短的路径，这与假设 是最短路径矛盾。

结合两种情况，我们可以得到

如果图有负权环，算法能够检测出来，这等价于对某个点 ，有 。假定输入图中没有负权环，那么从 到 的最短路径是没有环的，因此 。假定图中有负权环，那么一定存在一个只有起始顶点重复的负权环。若有其他重复点，就可以在重复点处把这个负权环拆成多个环，其中至少有一个环是负权环，否则总权重不会是负数。设这个负权环经过的顶点 ，并令 为该环上顶点编号的最大值。该环从 出发，经过的中间顶点都在 中，再回到 ，因此 至多为该环的权重，是一个负数，故 。

算法的伪代码如下。 

lastHop[0..n,0..n]
for v = 1 to n
    for w = 1 to n
        if (v,w) in E
            lastHop[v][w] = v
        else
            lastHop[v][w] = MAX
L[0..n,0..n,0..n]
for v = 1 to n
    for w = 1 to n
        if (v,w) in E
            L[0][v][w] = l_{vw}
        else if v == w
            L[0][v][w] = 0
        else
            L[0][v][w] = MAX
for k = 1 to n
    for v = 1 to n
        for w = 1 to n
            L[k][v][w] = min(L[k-1][v][w], L[k-1][v][k]+L[k-1][k][w])
            if L[k][v][w] < L[k-1][v][w]
                lastHop[v][w] = lastHop[k][w]

for v = 1 to n
    if L[n][v][v] < 0
        return N/A // there is a negative weight cycle

return L[n][v][w] for all v, w in V
算法的时间复杂度是 ，空间复杂度也是 。可以通过滚动数组将空间复杂度降至 ，因为 只依赖于 。

lastHop 数组记录了从 到 的最短路径的前继节点，因此可以在算法结束后沿着前继节点回溯，得到从 到 的最短路径。数组 lastHop 的大小是 ，因此回溯的时间复杂度是 。

实现参考 Floyd-Warshall。

最小生成树

给定一个连通的无向图 ，每条边 都有一个权重 ，最小生成树（Minimum Spanning Tree, MST）问题是找到 的一个生成树（spanning tree），使得该树的权重之和最小。生成树是一个子图，包含 的所有顶点，并且是一棵树，若以 表示其边集合，则 。

Prim 算法

Prim 算法是 1957 年由 Prim 提出的，算法的核心思想和 Dijkstra 算法类似，因此两年后（1959 年） Dijkstra 也独立给出了这个算法。不过稍后人们才意识到 Jarník 早在 1930 年就已经给出了这个算法，因此有时候也称为 Jarník-Prim 算法。

Prim 算法的核心思想对应的伪代码如下： 

T = {}
X = {s} // s is an arbitrary vertex in V

while exists(v, w), v in X, w not in X
    (v_min, w_min) = minimizing weight_{vw}
    X.add(w_min)
    T.add((v_min, w_min))

最直接的算法实现需要迭代 次，每次迭代需要遍历所有的边 ，因此时间复杂度是 。下面分析如何通过堆来加速整个算法，时间复杂度会降至 。

堆里面存放的是待处理的顶点 ，以及从 到该点的最小边的权重，即 当将 从 移动到 的时候，需要更新与 邻接的点 对应的最小边权重。 

X = {s}
T = {}
H = new Heap()
for v in V
    if v != s
        if (s, v) in E
            key[v] = weight_{sv}
            winner[v] = (s, v)
        else
            key[v] = MAX
            winner[v] = nullptr
        H.Push(v)

while !H.empty()
    w_min = H.Top()
    H.Pop()
    X.add(w_min)
    T.add(winner[w_min])
    // update key
    for Edge(w_min, v) in w_min.AdjacencyEdge()
        if v in X
            continue
        if weight_{w_minv} < key[v]
            key[v] = weight_{w_minv}
            winner[v] = (w_min, v)
            Delete v from H
            H.Push(v)
先分析一下时间复杂度，外层循环迭代 次；由于内层循环需要对每条边处理一次，因此迭代 次，循环里面有堆的操作，时间复杂度是 ，因此总的时间复杂度是 。

和 Dijkstra 算法类似，堆中待处理数据的组织方式可以选择。一种常见方法是将除起点外的所有顶点都放入堆，起点不入堆，其余顶点的候选边权重初始化为最大值，即上面的伪代码阐述的方式。另一种方式是堆中只放已经发现但尚未处理的顶点，初始时只处理起点，再将其邻接点加入堆。

这里也可以使用 IndexPriorityQueue 来实现，也可以使用普通的堆来实现，和 Dijkstra 算法一样。如果用普通堆实现，需要懒删除，导致性能下降，下降程度依赖于图的稀疏程度，边越多性能下降越严重，最多会慢一倍。

由于前面 Dijkstra 实现使用了 IndexPriorityQueue 和动态添加待处理的点，这里选择用普通的堆和一次性添加所有的点来实现 Prim 算法。参考 Prim。

最后，我们来证明算法的正确性。我们会首先给出最小瓶颈性质（The Minimum Bottleneck Property），然后证明 Prim 算法的输出满足最小瓶颈性质，最后证明满足最小瓶颈性质的树就是最小生成树。

给定一个图 ，每条边有一个权重 ，一条路径 的瓶颈（bottleneck）是指路径上权重最大的边。如果边 的权重等于所有 路径中的最小瓶颈，那么它满足最小瓶颈性质。

下面证明 Prim 算法选择的边满足最小瓶颈性质。假设 Prim 算法选择的边是 ，其中 ，。那么根据算法有 其中 。考虑任意一条 的路径 。由于 ，， 必然包含一条从 到 的边 ；因此其瓶颈至少为 ，从而不小于 。另一方面，边 本身构成一条 路径，因此 路径的最小瓶颈恰好为 。故 Prim 算法选择的边满足最小瓶颈性质。

下面证明，如果 是 的一个生成树，并且 满足最小瓶颈性质，那么 就是 的最小生成树。

想象从一个空图（只有顶点没有边）开始，逐步向图中添加边。有时一条边连接当前同一连通分量内的两个顶点，即 之间已存在一条路径 ，添加边 后会形成环，对连通分量的数量没有影响，称其为 C-类型边（C-type edge）。有时一条边将两个连通分量连接起来，即 分别属于 两个连通分量，添加后形成连通分量 ，称其为 F-类型边（F-type edge）。F-类型边不会形成环，如果存在一个环 ，那么去掉新加的边 后得到的路径 会连接 ，这与它们原本位于不同连通分量的假设矛盾。

是 的一个生成树，没有环，因此从只有顶点的图开始，每次添加的边都是 F-类型的边。一开始有 个顶点，即 个连通分量，每添加一条 F-类型的边，连通分量的数量就会减少一个，因此添加 条 F-类型的边后，所有顶点连接成一个连通分量，也就是 。因此 中有 条边。反之，如果添加 C-类型边，就会形成环，因此不可能得到生成树。Prim 算法每次从 中选择一个点，从 中选择一个点，这两个点分别属于两个不同的连通分量，因此 Prim 算法每次选择的边都是 F-类型边，所以 Prim 算法的输出是一个生成树。

有了上述铺垫，我们用反证法来证明：如果 是满足最小瓶颈性质的生成树，那么 就是最小生成树。假设 不是最小生成树，那么存在一个生成树 ，其权重小于 的权重。由于两棵树都是生成树，因此都有 条边， 中至少有一条边 不属于 。把这条边加到 中会形成一个环。根据最小瓶颈性质，边 的权重是连接 的路径的最小瓶颈，那么环中除 外的边的权重都不小于 的权重，因此在 中至少有一条边 的权重不小于 的权重。把 从 中去掉，得到的树 的权重不大于 的权重，因此也比 的权重更小。 有 条边且是连通的，在连接 的路径上去掉 后， 中的 不连通。那么 中的 连通，因此 是连通的。一增一减后， 有 条边，因此 是一个生成树。所以我们找到了权重更小的生成树 ，与假设矛盾，因此 就是最小生成树。

Kruskal 算法

Kruskal 的核心思想是每次选择权重最小的边，如果这条边连接了两个不同的连通分量，那么就把这条边加入到生成树中，否则的话就跳过这条边。算法的伪代码如下。 

T={}
sort(E)

for e in E
    if T union e does not create a cycle
        T.add(e)

return T
最朴素的实现复杂度是 ，其中 是点的个数， 是边的个数。因为上面的循环需要 次，每次中需要使用 BFS 或 DFS 来判断 是否已经连通了。下面介绍使用并查集（Union-Find）来加速这个过程，时间复杂度可以降到 ，这里也假设图是连通的，那么时间复杂度可以简化为 。

首先介绍并查集，它支持三种操作。

  • 初始化（initialize）：给定一个整数 ，创建一个包含 个元素的并查集，每个元素都在一个单独的集合中。
  • 查找（find）：给定一个元素，返回该元素所在集合的标识符（id）。如果两个元素的标识符相同，那么它们在同一个集合中。
  • 合并（union）：给定两个元素，将它们所在的集合合并成一个集合。

使用父指针树（parent tree）来实现并查集，parent[i] 表示元素 的父节点，如果 是一个集合的根节点，那么 parent[i] 就是 本身。初始化时，每个元素都是一个单独的集合，因此 parent[i]=i。find 操作就是沿着 parent 数组向上查找，直到找到一个元素 满足 parent[i]=i，这个元素就是所在集合的标识符。这里可以使用隔代压缩技术，在查找时使当前路径上的节点深度减半；或者使用递归方式的完全压缩技术，在查找时将当前路径上的所有节点直接连接到根节点上，但当树很深时可能导致栈溢出。因此我的实现采用了前者。union 操作就是将两个元素所在集合的根节点连接起来，即将其中一个根节点的 parent 指向另一个根节点。为了让树的深度尽可能小，额外使用一个数字 size[i] 来记录以 为根节点的集合大小，在合并时将较小的集合连接到较大的集合上。这样整个树的深度就不会超过 ，因此 find 和 union 的时间复杂度都是 。

参考实现 UnionFind

有了并查集，我们可以高效地判断一条边的两个端点是否在同一个集合中，即是否已经连通，从而优化 Kruskal 算法。 

T={}
sort(E)
UF = new UnionFind(n)
for e in E
    if UF.find(e.v) != UF.find(e.w)
        T.add(e)
        UF.union(e.v, e.w)

return T
首先对边按照权重进行排序，时间复杂度是 。对于简单图， 最多是 ，因此排序的时间复杂度也可以简化为 。然后循环迭代 次，每次迭代进行两次 find，时间复杂度是 。进行 次 union，时间复杂度是 ，因此总的时间复杂度是 。

参考实现 Kruskal

最后我们证明 Kruskal 算法的正确性。

首先，在处理完边 的迭代后，森林 中的 属于同一个连通分量。假定边 是 C-类型的边，那么 已经在同一个连通分量中；假定边 是 F-类型的边，那么 不在同一个连通分量中，当前迭代会把 加入到 ，此后 就在同一个连通分量中。

接着，我们证明 中 的路径 ，当算法迭代完所有的边的时候， 在 中的同一个连通分量。假定 的边分别是 ，其中 。在迭代到边 的时候，根据前面的证明， 在 中的同一个连通分量，因此迭代完所有的边的时候， 在 中的同一个连通分量。

下面证明 Kruskal 算法的输出 是生成树。很明显，输出没有环。因此我们只需要证明输出是连通的。给定一对点 ，由于 是连通的，那么 中有一条 的路径 ，根据前面的证明，迭代完所有的边的时候， 在 中的同一个连通分量，因此 是连通的。

我们在证明 Prim 的时候已经证明了满足最小瓶颈性质的生成树就是最小生成树，因此我们还需要证明 Kruskal 算法的输出满足最小瓶颈性质。这里使用反证法，假定 不满足最小瓶颈性质，那么 的路径 上每条边的权重小于 的权重，算法会先遍历权重小的边，那么根据前面的证明，迭代完 的所有的边的时候， 在 中的同一个连通分量，那么 就不会被加入到 中，与假设矛盾。