建图函数

环检测算法

DFS

BFS

这段 BFS 算法的思路：

1、构建邻接表，和之前一样，边的方向表示「被依赖」关系。

2、构建一个 indegree 数组记录每个节点的入度，即 indegree[i] 记录节点 i 的入度。

3、对 BFS 队列进行初始化，将入度为 0 的节点首先装入队列。

4、开始执行 BFS 循环，不断弹出队列中的节点，减少相邻节点的入度，并将入度变为 0 的节点加入队列。

5、如果最终所有节点都被遍历过（count 等于节点数），则说明不存在环，反之则说明存在环。

拓扑排序算法

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

DFS

BFS

二分图判定算法

二分图的顶点集可分割为两个互不相交的子集，图中每条边依附的两个顶点都分属于这两个子集，且两个子集内的顶点不相邻。 给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？

这就是图的「双色问题」，其实这个问题就等同于二分图的判定问题，如果你能够成功地将图染色，那么这幅图就是一幅二分图，反之则不是

DFS

BFS

Union-Find并查集

大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有两个功能：

  • 将两个元素添加到一个集合中。

  • 判断两个元素在不在同一个集合

名称"并查集"直接体现了它的核心功能：合并集合与查询元素所属集合。在英文中，它通常被称为"Union-Find"数据结构或"Disjoint-Set"数据结构。

并查集的基本思想是使用树形结构来表示每个集合，树的根节点作为集合的代表元素。

并查集核心特性：

  1. 快速查找：能够快速判断两个元素是否属于同一集合

  2. 快速合并：能够快速将两个集合合并为一个

  3. 路径压缩：优化查找操作，使树的高度尽量小

  4. 按秩合并：优化合并操作，减少树的高度增长

Union-Find 算法主要需要实现这两个 API：

这里所说的「连通」是一种等价关系，也就是说具有如下三个性质：

1、自反性：节点p和p是连通的。

2、对称性：如果节点p和q连通，那么q和p也连通。

3、传递性：如果节点p和q连通，q和r连通，那么p和r也连通。

比如说有一幅图，0～9 任意两个不同的点都不连通，调用connected都会返回 false，连通分量为 10 个。

如果现在调用union(0, 1)，那么 0 和 1 被连通，连通分量降为 9 个。

再调用union(1, 2)，这时 0,1,2 都被连通，调用connected(0, 2)也会返回 true，连通分量变为 8 个。

基础算法

设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。比如说刚才那幅 10 个节点的图，一开始的时候没有相互连通，就是这样：

如果某两个节点被连通，则让其中的（任意）一个节点的根节点接到另一个节点的根节点上：

这样，如果节点p和q连通的话，它们一定拥有相同的根节点：

至此，Union-Find 算法就基本完成了。

那么这个算法的复杂度是多少呢？我们发现，主要 APIconnected和union中的复杂度都是find函数造成的，所以说它们的复杂度和find一样。

find主要功能就是从某个节点向上遍历到树根，其时间复杂度就是树的高度。我们可能习惯性地认为树的高度就是logN，但这并不一定。logN的高度只存在于平衡二叉树，对于一般的树可能出现极端不平衡的情况，使得「树」几乎退化成「链表」，树的高度最坏情况下可能变成N。

所以说上面这种解法，find,union,connected的时间复杂度都是 O(N)。这个复杂度很不理想的，你想图论解决的都是诸如社交网络这样数据规模巨大的问题，对于union和connected的调用非常频繁，每次调用需要线性时间完全不可忍受。

平衡性优化

要知道哪种情况下可能出现不平衡现象，关键在于union过程：

我们一开始就是简单粗暴的把p所在的树接到q所在的树的根节点下面，那么这里就可能出现「头重脚轻」的不平衡状况，比如下面这种局面： 长此以往，树可能生长得很不平衡。我们其实是希望，小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。解决方法是额外使用一个size数组，记录每棵树包含的节点数，我们不妨称为「重量」：

比如说size[3] = 5表示，以节点3为根的那棵树，总共有5个节点。这样我们可以修改一下union方法：

这样，通过比较树的重量，就可以保证树的生长相对平衡，树的高度大致在logN这个数量级，极大提升执行效率。

此时，find,union,connected的时间复杂度都下降为 O(logN)，即便数据规模上亿，所需时间也非常少。

路径压缩

其实我们并不在乎每棵树的结构长什么样，只在乎根节点。

因为无论树长啥样，树上的每个节点的根节点都是相同的，所以能不能进一步压缩每棵树的高度，使树高始终保持为常数？ 如图所示，这样每个节点的父节点就是整棵树的根节点，find就能以 O(1) 的时间找到某一节点的根节点，相应的，connected和union复杂度都下降为 O(1)。

要做到这一点主要是修改find函数逻辑，非常简单，但你可能会看到两种不同的写法。

第一种是在find中加一行代码：

用语言描述就是，每次 while 循环都会把一对儿父子节点改到同一层，这样每次调用find函数向树根遍历的同时，顺手就将树高缩短了。

路径压缩的第二种写法是这样：

这个递归过程有点不好理解，你可以自己手画一下递归过程。我把这个函数做的事情翻译成迭代形式，方便你理解它进行路径压缩的原理：

这种路径压缩的效果如下： 比起第一种路径压缩，显然这种方法压缩得更彻底，直接把一整条树枝压平，一点意外都没有。就算一些极端情况下产生了一棵比较高的树，只要一次路径压缩就能大幅降低树高，从 摊还分析 的角度来看，所有操作的平均时间复杂度依然是 O(1)，所以从效率的角度来说，推荐你使用这种路径压缩算法。

另外，如果使用路径压缩技巧，那么size数组的平衡优化就不是特别必要了。所以你一般看到的 Union Find 算法应该是如下实现：

Union-Find 算法的复杂度可以这样分析：构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；连通两个节点union、判断两个节点的连通性connected、计算连通分量count所需的时间复杂度均为 O(1)。

到这里，相信你已经掌握了 Union-Find 算法的核心逻辑，总结一下我们优化算法的过程：

1、用parent数组记录每个节点的父节点，相当于指向父节点的指针，所以parent数组内实际存储着一个森林（若干棵多叉树）。

2、用size数组记录着每棵树的重量，目的是让union后树依然拥有平衡性，保证各个 API 时间复杂度为 O(logN)，而不会退化成链表影响操作效率。

3、在find函数中进行路径压缩，保证任意树的高度保持在常数，使得各个 API 时间复杂度为 O(1)。使用了路径压缩之后，可以不使用size数组的平衡优化。

优点

  1. 查找和合并操作的平均时间复杂度接近O(1)

  2. 实现简单，易于理解

  3. 空间复杂度低，只需要两个数组

  4. 适用于处理大量动态连通性问题

缺点

  1. 不支持分裂操作（将一个集合分成两个）

  2. 不方便查询集合中的所有元素

  3. 在某些特殊情况下，性能可能退化

应用场景

Kruskal最小生成树算法：在Kruskal算法中，并查集是核心数据结构。该算法按权重从小到大遍历边，使用并查集判断加入某条边是否会形成环，从而高效构建最小生成树。

网络连通性问题：并查集可高效解决动态连通性问题，比如判断网络中两个节点是否连通、社交网络中用户间的关系连接等。当关系变化时，只需执行简单的union操作，判断连通性时使用find操作即可。

等价类划分：在编译器设计、电路分析等领域，并查集可用于等价类识别与合并。当系统发现两个元素等价时执行union操作，需要判断等价关系时使用find操作，这种动态维护等价关系的能力正是并查集的优势所在。

判断无向图中的环：当向无向图中添加边时，如果边的两个端点已在同一个集合中，则添加这条边会形成环。在很多图算法和网络设计问题中都可以使用这一特性。

Kruskal 最小生成树算法

Kruskal 的 关键就是 并查集算法

先说「树」和「图」的根本区别：树不会包含环，图可以包含环。

如果一幅图没有环，完全可以拉伸成一棵树的模样。说的专业一点，树就是「无环连通图」。

那么什么是图的「生成树」呢，其实按字面意思也好理解，就是在图中找一棵包含图中的所有节点的树。专业点说，生成树是含有图中所有顶点的「无环连通子图」。

容易想到，一幅图可以有很多不同的生成树，比如下面这幅图，红色的边就组成了两棵不同的生成树： 对于加权图，每条边都有权重，所以每棵生成树都有一个权重和。比如上图，右侧生成树的权重和显然比左侧生成树的权重和要小。

那么最小生成树很好理解了，所有可能的生成树中，权重和最小的那棵生成树就叫「最小生成树」。

PS：一般来说，我们都是在无向加权图中计算最小生成树的，所以使用最小生成树算法的现实场景中，图的边权重一般代表成本、距离这样的标量。

所谓最小生成树，就是图中若干边的集合（我们后文称这个集合为mst，最小生成树的英文缩写），你要保证这些边：

1、包含图中的所有节点。

2、形成的结构是树结构（即不存在环）。

3、权重和最小。

前两条其实可以很容易地利用 Union-Find 算法做到，关键在于第 3 点，如何保证得到的这棵生成树是权重和最小的。

这里就用到了贪心思路：将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和mst中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入mst集合；否则，这条边不是最小生成树的一部分，不要把它加入mst集合。

这样，最后mst集合中的边就形成了最小生成树，算法代码如下：

复杂度分析：

假设一幅图的节点个数为V，边的条数为E，首先需要O(E)的空间装所有边，而且 Union-Find 算法也需要O(V)的空间，所以 Kruskal 算法总的空间复杂度就是O(V + E)。

时间复杂度主要耗费在排序，需要O(ElogE)的时间，Union-Find 算法所有操作的复杂度都是O(1)，套一个 for 循环也不过是O(E)，所以总的时间复杂度为O(ElogE)。

PRIM 最小生成树算法

Prim 算法也使用贪心思想来让生成树的权重尽可能小，也就是「切分定理」。

其次，Prim 算法使用BFS 算法思想和visited布尔数组避免成环，来保证选出来的边最终形成的一定是一棵树。

Prim 算法不需要事先对所有边排序，而是利用优先级队列动态实现排序的效果，所以 Prim 算法类似于 Kruskal 的动态过程。

切分定理：对于任意一种「切分」，其中权重最小的那条「横切边」一定是构成最小生成树的一条边。只要把图中的节点切成两个不重叠且非空的节点集合即可算作一个合法的「切分」

反证法证明：给定一幅图的最小生成树，那么随便给一种「切分」，一定至少有一条「横切边」属于最小生成树。假设这条「横切边」不是权重最小的，那说明最小生成树的权重和就还有再减小的余地，那这就矛盾了，最小生成树的权重和本来就是最小的，怎么再减？所以切分定理是正确的。

算法实现：Prim 算法的逻辑就是，每次切分都能找到最小生成树的一条边，然后又可以进行新一轮切分，直到找到最小生成树的所有边为止。

复杂度分析：

复杂度主要在优先级队列 pq 的操作上，由于 pq 里面装的是图中的「边」，假设一幅图边的条数为 E，那么最多操作 O(E) 次 pq。每次操作优先级队列的时间复杂度取决于队列中的元素个数，取最坏情况就是 O(logE)。

这种 Prim 算法实现的总时间复杂度是 O(ElogE)

Dijkstra 最短路径规划算法

算法签名：

输入是一幅图 graph 和一个起点 start，返回是一个记录最短路径权重的数组。

比方说，输入起点 start = 3，函数返回一个 int[] 数组，假设赋值给 distTo 变量，那么从起点 3 到节点 6 的最短路径权重的值就是 distTo[6]。标准的 Dijkstra 算法会把从起点 start 到所有其他节点的最短路径都算出来。

使用 distFromStart 变量记录从起点 start 到当前这个节点的距离。

普通 BFS 算法中，根据 BFS 的逻辑和无权图的特点，第一次遇到某个节点所走的步数就是最短距离，所以用一个 visited 数组防止走回头路，每个节点只会经过一次。

加权图中的 Dijkstra 算法和无权图中的普通 BFS 算法不同，在 Dijkstra 算法中，你第一次经过某个节点时的路径权重，不见得就是最小的，所以对于同一个节点，可能会经过多次，而且每次的 distFromStart 可能都不一样，取 distFromStart 最小的那次，就是从起点 start 到节点 5 的最短路径权重

Dijkstra 可以理解成一个带 dp table（或者说备忘录）的 BFS 算法，伪码如下：

计算起点到终点end的最短距离

A* 算法

Dijkstra算法的优点在于其简单可靠，能够保证找到全局最优解。然而，其缺点也明显：对大规模图的处理效率低下，因为它需要遍历整个图。

Astar 是一种 广搜的改良版。有的 Astar是 dijkstra 的改良版。

其实只是场景不同而已，在搜索最短路的时候， 如果是无权图（边的权值都是1） 那就用广搜，代码简洁，时间效率和 dijkstra 差不多 （具体要取决于图的稠密）如果是有权图（边有不同的权值），优先考虑 dijkstra。

而 Astar 关键在于 启发式函数， 也就是 影响 广搜或者 dijkstra 从 容器（队列）里取元素的优先顺序。

实现机制

启发式搜索的优势 A算法引入了启发式函数h(v)，它预估了从节点v到目标节点的最优路径成本。这使得A能够在搜索过程中具有方向性，优先探索那些更有可能导向目标的路径，从而减少不必要的探索，提高搜索效率。

实现机制

  • 评估函数：A*的关键在于f(v)=g(v)+h(v)，其中g(v)是从起点到节点v的实际成本，h(v)是启发式函数，通常表示 当前节点 到终点的距离。因此两者相加就是起点到终点的距离。

  • 开放与关闭集合：算法维护两个集合，开放集合存放待评估的节点，关闭集合存放已评估节点。每次迭代从开放集合中选择f值最小的节点进行扩展，直到目标节点被加入关闭集合。

BFS 是没有目的性的 一圈一圈去搜索， 而 A 是有方向性的去搜索*。

那么 A* 为什么可以有方向性的去搜索，它的如何知道方向呢？其关键在于 启发式函数。

计算两点距离通常有如下三种计算方式：这也一般被选为启发式函数，用来预估当前节点到终点的距离

  1. 曼哈顿距离，计算方式：d = abs(x1-x2)+abs(y1-y2)

  2. 欧氏距离（欧拉距离），计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )

  3. 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))

与Dijkstra的对比分析

  • 计算效率：A*由于采用了启发式信息，通常比Dijkstra算法更快找到解，尤其在复杂路网中更为显著。

  • 路径质量：理论上，只要启发式函数满足可接纳性条件，A*保证找到最短路径。Dijkstra同样保证最短路径，但缺乏效率优势。

  • 资源消耗：A*在内存使用上可能更高，因为它需要维护开放集合和关闭集合，而Dijkstra只需维护未访问集合和前驱节点映射。

  • 适用场景：Dijkstra适用于小型或中型规模、对实时性要求不高的场景；A*更适合大型图搜索或对实时性要求较高的无场景。

代码实现

实现代码如下：启发式函数 采用 欧拉距离计算方式

复杂度分析

A* 算法的时间复杂度 其实是不好去量化的，因为他取决于 启发式函数怎么写。

  • 最坏情况下，A* 退化成广搜，算法的时间复杂度 是 O(n * 2)，n 为节点数量。

  • 最佳情况，是从起点直接到终点，时间复杂度为 O(dlogd)，d 为起点到终点的深度。因为在搜索的过程中也需要堆排序，所以是 O(dlogd)。

实际上 A* 的时间复杂度是介于 最优 和最坏 情况之间， 可以 非常粗略的认为 A* 算法的时间复杂度是 O(nlogn)，n 为节点数量。

A* 算法的空间复杂度 O(b ^ d) ,d 为起点到终点的深度，b 是 图中节点间的连接数量

A* 的缺点

大家看上述 A * 代码的时候，可以看到 我们向队列里添加了很多节点，但真正从队列里取出来的 仅仅是 靠启发式函数判断 距离终点最近的节点。

相对于普通BFS，A* 算法只从 队列里取出 距离终点最近的节点。

那么问题来了，A* 在一次路径搜索中，大量不需要访问的节点都在队列里，会造成空间的过度消耗。

IDA* 算法对这一空间增长问题进行了优化，关于 IDA* 算法，后续再更新 //to do

另外还有一种场景 是 A* 解决不了的。

如果给出多个可能的目标，然后在这多个目标中选择最近的目标，这种 A* 就不擅长了， A* 只擅长给出明确的目标 然后找到最短路径。

如果是多个目标找最近目标（特别是潜在目标数量很多的时候），可以考虑 Dijkstra，BFS 或者 Floyd。