图算法的概念

图算法概述

图算法是通过在图中按特定方式遍历得到答案的算法。

已经介绍过的广度优先搜索和深度优先搜索是两种常见的图算法。除了两种搜索算法以外，常见的图算法还有以下三种。

• 拓扑排序：适用于有向无环图，图中的有向边决定顶点之间的相对顺序，将图中的顶点按相对顺序排序。一些有环图和无向图的场景也可以使用拓扑排序。

• 最短路：适用于带权图，计算从一个顶点到另一个顶点的权重最小的路径，路径的权重为该路径经过的所有边的权重之和。当图中的所有边的权重都是1 11时，退化为无权图，此时的最短路算法等价于广度优先搜索算法。

• 最小生成树：适用于带权图，在图中寻找一个包含所有顶点的无环连通树，满足树中的所有边的权重之和最小，这个树称为最小生成树。

拓扑排序

拓扑排序的概念

拓扑排序是将有向无环图中的顶点排序得到有序线性序列的算法。图中的每条有向边决定了顶点之间的相对顺序，如果有一条有向边从顶点u uu指向顶点v vv，则拓扑排序的结果应满足顶点u uu出现在顶点v vv之前。在有向无环图中，顶点之间的相对顺序是唯一的，因此一定存在拓扑排序。

同一个图可能有多种拓扑排序结果。例如，下图的拓扑排序可能有以下结果：[ 0 , 1 , 2 , 3 , 4 ] [0, 1, 2, 3, 4][0,1,2,3,4]、[ 0 , 1 , 3 , 2 , 4 ] [0, 1, 3, 2, 4][0,1,3,2,4]、[ 0 , 2 , 1 , 3 , 4 ] [0, 2, 1, 3, 4][0,2,1,3,4]。

拓扑排序的实现方式

拓扑排序可以基于广度优先搜索或深度优先搜索实现。

基于广度优先搜索的拓扑排序做法如下。

1. 计算每个顶点的入度，将入度为0 00的顶点入队列。

2. 每次将一个顶点出队列并添加到拓扑排序结果的末尾，将该顶点的每个后继顶点的入度减1 11。如果后继顶点的入度变为0 00，则将后继顶点入队列。

3. 重复上述操作，当所有顶点都遍历过之后，即可得到拓扑排序的结果。

基于深度优先搜索的拓扑排序做法如下。

1. 从任意一个顶点开始执行深度优先搜索，依次对该顶点的所有后继顶点执行深度优先搜索。

2. 当一个顶点的所有后继顶点都遍历过之后，将该顶点添加到拓扑排序结果的前端。

3. 如果存在其他尚未访问的顶点，则继续对尚未访问的顶点执行深度优先搜索。当所有顶点都遍历过之后，即可得到拓扑排序的结果。

拓扑排序的拓展场景

除了有向无环图以外，拓扑排序也适用于一些有环图和无向图的场景。

如果有向图中存在环，则环中的顶点循环依赖，因此不存在拓扑排序的结果。使用拓扑排序可以判断有向图中是否存在环。

对于无向图的场景，可以从度为1 11的顶点开始执行拓扑排序，寻找图的中心顶点。

最短路

带权图中，每条边都有权重，一条路径的权重为该路径经过的所有边的权重之和。最短路是在带权图中计算从一个顶点到另一个顶点的权重最小的路径的算法。

如果图中存在权重为负的环，且可以从源顶点到达该权重为负的环，则不存在权重最小的路径。以下只考虑图中不存在权重为负的环的情况。

常见的最短路算法包括 Bellman-Ford 算法、Dijkstra 算法和 Floyd-Warshall 算法。Bellman-Ford 算法和 Dijkstra 算法为单源最短路径算法，Floyd-Warshall 算法为所有顶点对最短路径算法。

以下用n nn表示图中的顶点数，m mm表示图中的边数。

Bellman-Ford 算法

Bellman-Ford 算法是最简单的单源最短路径算法，做法是对图中的所有边执行n − 1 n - 1n−1次遍历，得到从源顶点到每个顶点的最短路径权重。

创建长度为n nn的数组distances \textit{distances}distances作为结果数组，记录从源顶点到每个顶点的最短路径权重，用source \textit{source}source表示源顶点，初始时distances [ source ] = 0 \textit{distances}[\textit{source}] = 0distances[source]=0，distances \textit{distances}distances中的其余元素都是∞ \infty∞。

将遍历到的边的起点、终点和权重分别记为start \textit{start}start、end \textit{end}end和weight \textit{weight}weight，如果distances [ start ] ≠ ∞ \textit{distances}[\textit{start}] \ne \inftydistances[start]=∞且distances [ end ] > distances [ start ] + weight \textit{distances}[\textit{end}] > \textit{distances}[\textit{start}] + \textit{weight}distances[end]>distances[start]+weight，则将distances [ end ] \textit{distances}[\textit{end}]distances[end]的值更新为distances [ start ] + weight \textit{distances}[\textit{start}] + \textit{weight}distances[start]+weight。

初始时可以确定源顶点source \textit{source}source对应的最短路径权重是0 00。每一次遍历之后，可以确定图中的一个顶点对应的最短路径权重，n − 1 n - 1n−1次遍历之后即可得到从源顶点到每个顶点的最短路径权重。

使用 Bellman-Ford 算法时，图中可以存在权重为负的边。

Bellman-Ford 算法的时间复杂度是O ( n m ) O(nm)O(nm)，空间复杂度是O ( 1 ) O(1)O(1)（返回值不计入空间复杂度）。

Bellman-Ford 算法的实现如下。输入参数为边数组表示的图edges \textit{edges}edges、图中顶点数n nn和源顶点source \textit{source}source（0 ≤ source < n 0 \le \textit{source} < n0≤source<n）。边数组中的每个元素是长度为3 33的数组[ i , j , w ] [i, j, w][i,j,w]，表示图中存在一条权重是w ww的边( i , j ) (i, j)(i,j)。

classSolution{publicint[]bellmanFord(int[][]edges,intn,intsource){int[]distances=newint[n];Arrays.fill(distances,Integer.MAX_VALUE);distances[source]=0;for(inti=1;i<n;i++){for(int[]edge:edges){intstart=edge[0],end=edge[1],weight=edge[2];if(distances[start]!=Integer.MAX_VALUE&&distances[end]>distances[start]+weight){distances[end]=distances[start]+weight;}}}returndistances;}}

Dijkstra 算法

Dijkstra 算法是优化的单源最短路径算法，做法是对图中的顶点执行n nn次循环，得到从源顶点到每个顶点的最短路径权重。

每次循环时，从尚未确定最短路径权重的顶点中找到最短路径权重最小的顶点，将该顶点的状态更新为确定最短路径权重，并使用该顶点的最短路径权重更新该顶点的所有后继顶点的最短路径权重。由于每次循环都能确定一个顶点的最短路径权重，因此经过n nn次循环之后即可得到每个顶点的最短路径权重。

寻找最短路径权重最小的顶点有两种做法，第一种做法是枚举所有尚未确定最短路径权重的顶点，第二种做法是维护小根堆。

使用 Dijkstra 算法时，图中的所有边的权重都必须非负。

Dijkstra 算法的时间复杂度是O ( n 2 ) O(n^2)O(n2)或O ( ( n + m ) log ⁡ n ) O((n + m) \log n)O((n+m)logn)，取决于实现方式是基于枚举实现还是基于小根堆实现，空间复杂度是O ( n ) O(n)O(n)。

Dijkstra 算法的基于枚举实现和基于小根堆实现如下。输入参数为邻接数组表示的图graph \textit{graph}graph和源顶点source \textit{source}source（0 ≤ source < n 0 \le \textit{source} < n0≤source<n）。邻接数组的长度是n nn，对于0 ≤ i < n 0 \le i < n0≤i<n，graph [ i ] \textit{graph}[i]graph[i]为所有以顶点i ii为起点的边的终点和权重的集合，如果[ j , w ] ∈ graph [ i ] [j, w] \in \textit{graph}[i][j,w]∈graph[i]，则图中存在一条权重是w ww的边( i , j ) (i, j)(i,j)。

classSolution{publicint[]dijkstra(int[][][]graph,intsource){intn=graph.length;int[]distances=newint[n];Arrays.fill(distances,Integer.MAX_VALUE);distances[source]=0;boolean[]visited=newboolean[n];for(inti=0;i<n;i++){intcurr=-1;for(intj=0;j<n;j++){if(!visited[j]&&(curr<0||distances[curr]>distances[j])){curr=j;}}visited[curr]=true;for(int[]adjacent:graph[curr]){intnext=adjacent[0],weight=adjacent[1];distances[next]=Math.min(distances[next],distances[curr]+weight);}}returndistances;}}

classSolution{publicint[]dijkstra(int[][][]graph,intsource){intn=graph.length;int[]distances=newint[n];Arrays.fill(distances,Integer.MAX_VALUE);distances[source]=0;PriorityQueue<int[]>pq=newPriorityQueue<int[]>((a,b)->a[1]-b[1]);pq.offer(newint[]{source,0});while(!pq.isEmpty()){int[]pair=pq.poll();intcurr=pair[0],distance=pair[1];if(distances[curr]<distance){continue;}for(int[]adjacent:graph[curr]){intnext=adjacent[0],weight=adjacent[1];if(distances[next]>distance+weight){distances[next]=distance+weight;pq.offer(newint[]{next,distances[next]});}}}returndistances;}}

Floyd-Warshall 算法

Floyd-Warshall 算法用于计算所有顶点对最短路径，考虑最短路径的中间顶点。

用distances [ i ] [ j ] \textit{distances}[i][j]distances[i][j]表示从顶点i ii到顶点j jj的最短路径权重。从顶点i ii到顶点j jj的最短路径有两种情况，一是存在一条边( i , j ) (i, j)(i,j)，二是从顶点i ii先到中间顶点k kk然后到顶点j jj。

Floyd-Warshall 算法的具体做法是：对于每个0 ≤ k < n 0 \le k < n0≤k<n，遍历每一对顶点( i , j ) (i, j)(i,j)，当distances [ i ] [ j ] > distances [ i ] [ k ] + distances [ k ] [ j ] \textit{distances}[i][j] > \textit{distances}[i][k] + \textit{distances}[k][j]distances[i][j]>distances[i][k]+distances[k][j]时将distances [ i ] [ j ] \textit{distances}[i][j]distances[i][j]更新为distances [ i ] [ k ] + distances [ k ] [ j ] \textit{distances}[i][k] + \textit{distances}[k][j]distances[i][k]+distances[k][j]，遍历结束之后即可得到所有顶点对的最短路径权重。

实现方面，当给定的图是邻接矩阵时，可以直接在邻接矩阵上更新所有顶点对的最短路径权重。

使用 Floyd-Warshall 算法时，图中可以存在权重为负的边。

Floyd-Warshall 算法的时间复杂度是O ( n 3 ) O(n^3)O(n3)，空间复杂度是O ( 1 ) O(1)O(1)（返回值不计入空间复杂度）。

Floyd-Warshall 算法的实现如下。输入参数为邻接矩阵表示的图matrix \textit{matrix}matrix。矩阵的行数和列数都是n nn，对于0 ≤ i , j < n 0 \le i, j < n0≤i,j<n，matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]的值如下。

• 如果i = j i = ji=j，则matrix [ i ] [ j ] = 0 \textit{matrix}[i][j] = 0matrix[i][j]=0。

• 如果i ≠ j i \ne ji=j且存在边( i , j ) (i, j)(i,j)，则matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]为边( i , j ) (i, j)(i,j)的权重。

• 如果i ≠ j i \ne ji=j且不存在边( i , j ) (i, j)(i,j)，则matrix [ i ] [ j ] = ∞ \textit{matrix}[i][j] = \inftymatrix[i][j]=∞。

classSolution{publicint[][]floydWarshall(int[][]matrix){intn=matrix.length;for(intk=0;k<n;k++){for(inti=0;i<n;i++){for(intj=0;j<n;j++){matrix[i][j]=Math.min(matrix[i][j],matrix[i][k]+matrix[k][j]);}}}returnmatrix;}}

最小生成树

无向带权连通图中的最小生成树是包含图中所有顶点的子图，该子图为连通无环图，子图中的所有边的权重之和最小，由于子图满足连通和无环，因此子图一定是树的结构。用n nn表示图中的顶点数，则最小生成树包含n − 1 n - 1n−1条边，且这些边的权重之和最小。

同一个图中的最小生成树可能不唯一，但是最小生成树中的边的权重之和最小值唯一。如果一个图中有多个可能的最小生成树，则每个最小生成树中的边的权重之和相同。

构建最小生成树的思想是，初始时图中的n nn个顶点都是独立的，每次选一条边加入最小生成树，使得所选的边不形成环且权重之和最小，重复n − 1 n - 1n−1次操作之后，选定的n − 1 n - 1n−1条边将n nn个顶点连接，得到最小生成树。

构建最小生成树的算法有 Kruskal 算法和 Prim 算法。

以下用n nn表示图中的顶点数，m mm表示图中的边数。

Kruskal 算法

Kruskal 算法构建最小生成树的做法是：每次在尚未选取的边中选取一条权重最小且不会产生环的边，将这条边作为最小生成树中的一条边，直到所有的顶点属于同一个连通分量。

判断选取一条边是否会产生环的做法是，判断这条边连接的两个顶点是否属于同一个连通分量，如果属于同一个连通分量则选取这条边之后会产生环，如果不属于同一个连通分量则选取这条边之后不会产生环。选取一条边之后，需要将这条边连接的两个顶点合并到同一个连通分量。

连通性问题可以使用并查集解决。并查集支持合并与查找的操作，Kruskal 算法是并查集的应用场景之一。高级数据结构部分将会具体介绍并查集。

Kruskal 算法的时间复杂度是O ( n + m log ⁡ m ) O(n + m \log m)O(n+mlogm)，空间复杂度是O ( n + m ) O(n + m)O(n+m)。

由于 Kruskal 算法的时间复杂度和边数有关，因此 Kruskal 算法适用于边稀疏图。

Prim 算法

Prim 算法构建最小生成树的做法是：任选一个顶点开始构建最小生成树，初始时的最小生成树只有选定的顶点，每次在尚未选取的顶点中选取与最小生成树连接的边的权重最小的顶点，将该顶点和对应的边添加到最小生成树中，直到所有顶点都被添加到最小生成树中，此时的生成树为最小生成树。

Prim 算法的时间复杂度是O ( n 2 ) O(n^2)O(n2)，空间复杂度是O ( n ) O(n)O(n)。

由于 Prim 算法的时间复杂度只和顶点数有关，因此 Prim 算法适用于边稠密图。

目录

1. 拓扑排序题目：从给定原材料中找到所有可以做出的菜
2. 拓扑排序题目：找到最终的安全状态
3. 拓扑排序题目：最小高度树
4. 拓扑排序题目：喧闹和富有
5. 拓扑排序题目：项目管理
6. 拓扑排序题目：奇怪的打印机 II
7. 最短路题目：网络延迟时间
8. 最短路题目：阈值距离内邻居最少的城市
9. 最短路题目：使网格图至少有一条有效路径的最小代价
10. 最短路题目：概率最大的路径
11. 最短路题目：细分图中的可到达结点
12. 最小生成树题目：连接所有点的最小费用
13. 最小生成树题目：找到最小生成树里的关键边和伪关键边