文章目录图算法概述拓扑排序拓扑排序的概念拓扑排序的实现方式拓扑排序的拓展场景最短路Bellman-Ford 算法Dijkstra 算法Floyd-Warshall 算法最小生成树Kruskal 算法Prim 算法目录图算法概述图算法是通过在图中按特定方式遍历得到答案的算法。已经介绍过的广度优先搜索和深度优先搜索是两种常见的图算法。除了两种搜索算法以外常见的图算法还有以下三种。拓扑排序适用于有向无环图图中的有向边决定顶点之间的相对顺序将图中的顶点按相对顺序排序。一些有环图和无向图的场景也可以使用拓扑排序。最短路适用于带权图计算从一个顶点到另一个顶点的权重最小的路径路径的权重为该路径经过的所有边的权重之和。当图中的所有边的权重都是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]。拓扑排序的实现方式拓扑排序可以基于广度优先搜索或深度优先搜索实现。基于广度优先搜索的拓扑排序做法如下。计算每个顶点的入度将入度为0 00的顶点入队列。每次将一个顶点出队列并添加到拓扑排序结果的末尾将该顶点的每个后继顶点的入度减1 11。如果后继顶点的入度变为0 00则将后继顶点入队列。重复上述操作当所有顶点都遍历过之后即可得到拓扑排序的结果。基于深度优先搜索的拓扑排序做法如下。从任意一个顶点开始执行深度优先搜索依次对该顶点的所有后继顶点执行深度优先搜索。当一个顶点的所有后继顶点都遍历过之后将该顶点添加到拓扑排序结果的前端。如果存在其他尚未访问的顶点则继续对尚未访问的顶点执行深度优先搜索。当所有顶点都遍历过之后即可得到拓扑排序的结果。拓扑排序的拓展场景除了有向无环图以外拓扑排序也适用于一些有环图和无向图的场景。如果有向图中存在环则环中的顶点循环依赖因此不存在拓扑排序的结果。使用拓扑排序可以判断有向图中是否存在环。对于无向图的场景可以从度为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]0distances \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}source0 ≤ source n 0 \le \textit{source} n0≤sourcen。边数组中的每个元素是长度为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[]distancesnewint[n];Arrays.fill(distances,Integer.MAX_VALUE);distances[source]0;for(inti1;in;i){for(int[]edge:edges){intstartedge[0],endedge[1],weightedge[2];if(distances[start]!Integer.MAX_VALUEdistances[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((nm)logn)取决于实现方式是基于枚举实现还是基于小根堆实现空间复杂度是O ( n ) O(n)O(n)。Dijkstra 算法的基于枚举实现和基于小根堆实现如下。输入参数为邻接数组表示的图graph \textit{graph}graph和源顶点source \textit{source}source0 ≤ source n 0 \le \textit{source} n0≤sourcen。邻接数组的长度是n nn对于0 ≤ i n 0 \le i n0≤ingraph [ 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){intngraph.length;int[]distancesnewint[n];Arrays.fill(distances,Integer.MAX_VALUE);distances[source]0;boolean[]visitednewboolean[n];for(inti0;in;i){intcurr-1;for(intj0;jn;j){if(!visited[j](curr0||distances[curr]distances[j])){currj;}}visited[curr]true;for(int[]adjacent:graph[curr]){intnextadjacent[0],weightadjacent[1];distances[next]Math.min(distances[next],distances[curr]weight);}}returndistances;}}classSolution{publicint[]dijkstra(int[][][]graph,intsource){intngraph.length;int[]distancesnewint[n];Arrays.fill(distances,Integer.MAX_VALUE);distances[source]0;PriorityQueueint[]pqnewPriorityQueueint[]((a,b)-a[1]-b[1]);pq.offer(newint[]{source,0});while(!pq.isEmpty()){int[]pairpq.poll();intcurrpair[0],distancepair[1];if(distances[curr]distance){continue;}for(int[]adjacent:graph[curr]){intnextadjacent[0],weightadjacent[1];if(distances[next]distanceweight){distances[next]distanceweight;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≤kn遍历每一对顶点( 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,jnmatrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]的值如下。如果i j i jij则matrix [ i ] [ j ] 0 \textit{matrix}[i][j] 0matrix[i][j]0。如果i ≠ j i \ne jij且存在边( 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 jij且不存在边( i , j ) (i, j)(i,j)则matrix [ i ] [ j ] ∞ \textit{matrix}[i][j] \inftymatrix[i][j]∞。classSolution{publicint[][]floydWarshall(int[][]matrix){intnmatrix.length;for(intk0;kn;k){for(inti0;in;i){for(intj0;jn;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(nmlogm)空间复杂度是O ( n m ) O(n m)O(nm)。由于 Kruskal 算法的时间复杂度和边数有关因此 Kruskal 算法适用于边稀疏图。Prim 算法Prim 算法构建最小生成树的做法是任选一个顶点开始构建最小生成树初始时的最小生成树只有选定的顶点每次在尚未选取的顶点中选取与最小生成树连接的边的权重最小的顶点将该顶点和对应的边添加到最小生成树中直到所有顶点都被添加到最小生成树中此时的生成树为最小生成树。Prim 算法的时间复杂度是O ( n 2 ) O(n^2)O(n2)空间复杂度是O ( n ) O(n)O(n)。由于 Prim 算法的时间复杂度只和顶点数有关因此 Prim 算法适用于边稠密图。目录拓扑排序题目从给定原材料中找到所有可以做出的菜拓扑排序题目找到最终的安全状态拓扑排序题目最小高度树拓扑排序题目喧闹和富有拓扑排序题目项目管理拓扑排序题目奇怪的打印机 II最短路题目网络延迟时间最短路题目阈值距离内邻居最少的城市最短路题目使网格图至少有一条有效路径的最小代价最短路题目概率最大的路径最短路题目细分图中的可到达结点最小生成树题目连接所有点的最小费用最小生成树题目找到最小生成树里的关键边和伪关键边