建图是一个机械劳作 邻接矩阵 邻接矩阵是一个二维数组，其行和列都对应图中的顶点。如果顶点i和顶点j之间存在边，则矩阵中的i,j 位置的元素为1（对于无权图），或为边的权重（对于有权图）。如果i=j，则通常为0，表示顶点不会与自己相连 一般来说，题目给出的都是邻接矩阵的形式。 例如743. 网络延迟时间 这个题目就是给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。 本篇主要讨论如何将邻接矩阵转换成其它的存图方式 邻接表 邻接表是表示图中顶点之间相邻关系的一种方式。对于图中的每一个顶点，邻接表包含了与该顶点直接相连的所有顶点的列表。 12345678public int networkDelayTime(int[][] times, int n, int k) { List<int[]> g[] = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayL ...

SPFA算法 概念 SPFA算法是一种基于Bellman-Ford算法的改进版本，它用于计算图中各节点到源节点的最短路径。与Bellman-Ford算法不同的是，SPFA算法使用了队列来优化计算，从而在某些情况下加速了计算过程。 SPFA算法的基本思想是从源节点开始，将源节点放入队列中，然后不断从队列中取出节点，考察它的邻接节点，以更新到这些邻接节点的最短距离。如果某个节点的最短距离被更新，且该节点不在队列中，那么将该节点加入队列中，以便后续继续考察。 复杂度是O(V*E) 步骤 初始化：将源节点的最短距离设置为0，其他节点的最短距离设置为无穷大（或一个足够大的值），并将源节点加入队列中。 迭代处理队列中的节点： 从队列中取出一个节点。 考察该节点的所有邻接节点，如果通过当前节点到达邻接节点的路径比已知的最短路径更短，则更新邻接节点的最短路径。 如果邻接节点的最短路径被更新，且邻接节点不在队列中，将它加入队列中。 重复步骤2，直到队列为空。 最短路径计算完成后，可以从源节点到任意目标节点的最短路径已知。 原则 只让当前点能到达的点入队 如果一个点已经在队列里， ...

网络流 概念 网络流是一种抽象模型，它通常表示为一个有向图，其中节点代表各种资源的位置，边表示资源在节点之间的流动。每条边上都有一个容量，表示资源可以通过该边的最大数量。网络流问题的目标通常是找到从一个节点到另一个节点的流量分布，以最大化或最小化某种性能度量，例如最大流问题和最小割问题。 流（Flow）：表示资源在网络中的分配和传输。流量可以通过图中的边流动，但不能超过每条边的容量限制。 容量（Capacity）：每条边上的容量表示该边允许的最大流量。流量不得超过容量。 源点和汇点（Source and Sink）：源点是网络中资源的起始位置，汇点是资源的目标位置。网络流问题的目标通常是从源点到汇点传输最大量的资源。 最大流问题（Maximum Flow Problem）：在给定网络中寻找从源点到汇点的最大流量，同时满足容量限制。 最小割问题（Minimum Cut Problem）：在给定网络中找到一组边，通过删除这些边可以分离源点和汇点，同时最小化被切割的容量总和。 Ford-Fulkerson算法 Ford-Fulkerson算法是一种在网络流中寻找最大流的贪心算法。该算法通 ...

Floyd算法 概念 Floyd算法，也称为Floyd-Warshall算法，是一种用于求解图中所有顶点对之间最短路径的算法。 它是一种动态规划算法，适用于有向图或带权图，可以处理负权边（但不能包含负权回路，负权回路会导致无限小路径）。 伪代码 12345for(k : V) for(i : V) for(j : V) if(d(i, k) + d(k, j) < d(i, j)) d(i, j) = d(i, k) + d(k, j) 算法过程 该算法的本质是动态规划，以状态转移方程的形式描述如下，其中 dp[k][i][j] 表示 经过前 k 个顶点的松弛，得到的顶点 i 到顶点 j 的最短路径长度 。注意第一维的 k 表示 k 个顶点，第二维和第三维表示具体的顶点。 定义: dp[k][i][j] 表示经过前 k 个顶点的松弛，得到的顶点 i 到顶点 j 的最短路径长度。 边界: dp[0][i][j] = i == j ? 0 : (g[i][j] == 0 ? Inf : g[i][j]) 递推: dp[k][i][j] = min& ...

Dijkstra算法 概念 Dijkstra 算法是一个可以解决单一源点最短路径问题的经典算法，本质上是对广度优先搜索（BFS）的一个推广，只是把 BFS 维护的栈换成了优先队列。 Dijkstra算法成立的前提条件是不存在负权的边，这意味任何一条路径，从起点开始到路径中每个点的距离都是依次递增的。所以按照递增的顺序来依次计算出最短路径也就是Dijkstra算法了 每次循环都会增多一个保证已经找到最短路的点。 直观来说，如果我们已经求出了k个离源点距离最近的点，以及它们各自的距离，那么到源点距离第k+1近的点，它到源点的最短路径只能经过这前k个点——如果经过了其他点，那么这个其他点显然离源点更近，那这个点一定不是第k+1近了。既然只经过这前k个点，那么只用这前k个点放缩就可以找到那个最短路径了。再加上前k-1个点上一轮已经放缩过，所以每一轮只需要用新加入的节点进行放缩就行了。 无法处理有负边的图 举例： graph LR s --2--> u -- -3--> v s --1--> v 第一次贪心得到的点的路径s->v不是最短路 拓展 ...