并查集：
并查集（Union−FindUnion-FindUnion−Find）是一种用于管理不相交集合的高效数据结构，主要解决元素的分组、合并与连通性查询问题。主要分成查询（FindFindFind）和合并（UniteUniteUnite）两个操作。
模板代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
生成树：
在连通图 GGG 中，对于 ∀u、v∈G.V\forall u、v\in G.V∀u、v∈G.V，有且仅有一条路，且生成树中不存在回路。
最小生成树：
是所有的生成树中边权值和最小的一棵生成树。常见算法有 KruskalKruskalKruskal（克鲁斯卡尔）和 PrimPrimPrim（普里姆）
求最小生成树的方法：
· KRUSKAL 算法：
1、将所有的边按从小到大顺序排序
2、按排序顺序选择联通 u、vu、vu、v 两个结点的边
3、通过并查集判断 u、vu、vu、v 两个结点是否联通
4、如果不联通则合并两个结点
模板代码：
时间复杂度：O(ElogE)O(E\log E)O(ElogE)
空间复杂度：O(V+E)O(V+E)O(V+E)
· PRIM算法：
1、选择初始结点
2、从当前结点开始找到相邻边权值最小的结点，加入最小生成树中
3、加入的结点继续更新相邻结点的边权值，重复执行直到更新所有点
模板代码：
时间复杂度：O(V2)O(V^2)O(V2)
空间复杂度：O(V+E)O(V+E)O(V+E)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最短路算法：
即求从结点uuu到结点vvv所有的道路中边权值之和最短的一条道路的算法。分为单源最短路和多源最短路算法。单源最短路即从定结点uuu到所有其它结点vvv的算法，而多源最短路算法可以求∀u∈G.V\forall u \in G.V∀u∈G.V作为起点到其它结点vvv的最短路。
单源最短路算法：
常见的有 DijkstraDijkstraDijkstra（迪杰斯特拉）、Bellman−FordBellman-FordBellman−Ford（贝尔曼-福特）和 SPFASPFASPFA 三个算法。
求单源最短路的方法：
· DIJKSTRA
DijkstraDijkstraDijkstra 的算法思想和 PrimPrimPrim 算法找最小生成树类似，采用“蓝白点”思想。
1、从当前结点开始找到相邻路径长度最短的结点
2、从新结点开始继续更新相邻结点的最短路，重复执行直到更新（松弛）所有点
模板代码：
时间复杂度：O(V2)O(V^2)O(V2)
空间复杂度：O(V+E)O(V+E)O(V+E)
DIJKSTRA 不适用的情况：
根据 DijkstraDijkstraDijkstra 算法的逻辑和流程，可以进行简单的模拟，易证它不适用于出现 负边权 的情况。
· BELLMAN-FORD：
不同于 DijkstraDijkstraDijkstra 算法，Bellman−FordBellman-FordBellman−Ford 算法枚举的是边而非结点。
1、遍历所有的边
2、从边的起点做到终点的松弛操作
3、如果没有进行过松弛操作则退出循环
模板代码：
时间复杂度：O(VE)O(VE)O(VE)
空间复杂度：O(V+E)O(V+E)O(V+E)
BELLMAN-FORD 不适用的情况：
Bellman−FordBellman-FordBellman−Ford 可以用于负权边的情况，不适用于负权回路。
· SPFA：
SPFASPFASPFA（Shortest Path Faster AlgorithmShortest\,\,Path\,\,Faster\,\,AlgorithmShortestPathFasterAlgorithm）是 Bellman−FordBellman-FordBellman−Ford 算法的进阶版本，通过队列来对其进行优化。
模板代码：
时间复杂度：O(kV)O(kV)O(kV)（kkk为常数，通常是在 [2,3][2,3][2,3] 之间）
空间复杂度：O(V+E)O(V+E)O(V+E)
队列空间复杂度：0<x≤O(V)0< x\leq O(V)0<x≤O(V)
多源最短路算法：
一般用 Floyd−WarshallFloyd-WarshallFloyd−Warshall 算法（也有版本叫它 Floyed−WarshallFloyed-WarshallFloyed−Warshall）。
求多远最短路的方法：
· FLOYD-WARSHALL：
Floyd−WarshallFloyd-WarshallFloyd−Warshall算法可能是大多数人最喜欢的方法。其核心思想是动态规划，把每个结点作为中转点、起点和终点进行计算。注意不能够把它循环顺序反过来，否则结果会出问题。
模板代码：
时间复杂度：O(V3)O(V^3)O(V3)
空间复杂度：O(V2)O(V^2)O(V2)
FLOYD-WARSHALL 不适用的情况
Floyd−WarshallFloyd-WarshallFloyd−Warshall 不适用于出现负权回路的情况。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
备注：
符号解释：
VVV：表示点的数量
EEE：表示边的数量
G.VG.VG.V：指点的集合
G.EG.EG.E：指边的集合
实际上只不过是个上课笔记
