图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
其中每个元素称为结点(node),每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
如图是一棵树：
一棵树中至少有1个结点，即根结点。
一个结点的子树个数，称为这个结点的度（如结点1的度为3，结点3的度为0）。
度为0的结点称为叶结点（leaf）（如结点3、5、6、8、9）。
树中各结点的度的最大值称为这棵树的度（此树的度为3）。
上端结点为下端结点的父结点，称同一个父结点的多个子结点为兄弟结点（如结点1是结点2、3、4的父结点，结点 2、3、4是结点1的子结点，它们又是兄弟结点）。
遍历
树结构解决问题时，按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。
先序(根)遍历
先访问根结点，再从左到右按照先序思想遍历各棵子树（如，上图先序遍历的结果为125634789）。
后序（根）遍历
先从左到右遍历各棵子树，再访问根结点（如，上图后序遍历的结果为562389741）。
层次遍历
按层次从小到大逐个访问，同一层次按照从左到右的次序（如，上图层次遍历的结果为123456789）。
叶结点遍历
即从左到右遍历所有叶节点（如，上图叶节点遍历的结果为56389）。
二叉树
二叉树是一种特殊的树型结构，它是度数为2的树，即二叉树的每个结点最多有两个子结点。
每个结点的子结点分别称为左儿子、右儿子。
五种基本形态
性质
性质一
二叉树的第i层最多有2i-1个结点（i>=1）（可用二进制性质解释。）。
性质二
深度为k的二叉树至多有2k–1个结点（k>=1）。
性质三
任意一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。
性质四
有n个结点的完全二叉树的深度为floor(log2n)+1。
性质五
一棵n个结点的完全二叉树，对任一个结点(编号为i)，有：如果i=1，则结点i为根，无父结点；如果i>1,则其父结点编号为floor（i/2），如果i为父节点编号，那么2i是左孩子，2i+1是右孩子。
图A-满二叉树
图B-完全二叉树
编号示意图
遍历
二叉树的遍历是指按一定的规律和次序访问树中的各个结点。
遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。
先序遍历
若二叉树为空，则空操作，否则：
访问根结点、先序遍历左子树、先序遍历右子树
先序遍历此图结果为：124753689
中序遍历
若二叉树为空，则空操作，否则：
中序遍历左子树、访问根结点、中序遍历右子树
中序遍历上图结果为：742513869
后序遍历
若二叉树为空，则空操作，否则：
后序遍历左子树、后序遍历右子树、访问根结点
后序遍历上图结果为：745289631
已知先序序列和中序序列可唯一确定一棵二叉树；
已知中序序列和后序序列可唯一确定一棵二叉树；
已知先序序列和后序序列不可唯一确定一棵二叉树；
二叉树操作（建树、删除、输出）
普通树转二叉树
由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转换成二叉树进行操作。
通用法则：“左孩子，右兄弟”
建树
删除树
插入一个结点到排序二叉树中
在排序二叉树中查找一个数
扩展二叉树
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用“.”补齐，称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列，要求输出其中序和后序序列。
输入样例：
ABD..EF..G..C..
输出样例：
DBFEGAC
DFGEBCA
二叉树的建立和输出
以二叉链表作存储结构，建立一棵二叉树，并输出该二叉树的先序、中序、后序遍历序列、高度和结点总数。
输入样例：
12##3##
//#为空
输出样例：
123
//先序排列
213
//中序排列
231
//后序排列
//高度
//结点总数
因为本蒟蒻不太会用指针，所以自己写了一个不带指针的，代码很丑，见谅QwQ
P1030 求先序排列
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入：
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与 后序排列。
输出：
1行，表示一棵二叉树的先序。
输入样例：
BADC
BDCA
输出样例：
ABCD
分析
中序为BADC，后序为BDCA，所以A为根结点，B、DC分别为左右子树的中序序列，B、DC分别为左右子树的后序序列。然后再递归处理中序为B，后序为B的子树和中序为DC，后序为DC的子树。
自己用char数组写的代码QwQ
求后序排列
输入：
二叉树的前序序列与中序序列
输出：
二叉树的后序序列
样例输入：
abcdefg
cbdafeg
样例输出：
cdbfgea
因为有小可爱说我的代码在输入时的处理不清楚，所以又写了一个版本QwQ
表达式树
关于表达式树，我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如，对于下图的遍历结果如下，它们对应着表达式的3种表示方法。
-+a*b-cd/ef (前缀表示、波兰式)
a+b*(c-d)-e/f (中缀表示)
abcd-*+ef/- (后缀表示、逆波兰式)
哈夫曼树
前置知识
如果数据元素集合中的各元素之间存在任意的关系，则此数据结构称为图。
如果将数据元素抽象为顶点(V)，元素之间的关系用边(E)表示，则图亦可以表示为G=（V，E），其中V是顶点的有穷（非空）集合，E为边的集合。
边权
离散数学或数据结构中，图的每条边上带的一个数值，它代表的含义可以是长度等等，这个值就是边权。
顶点的度
入度（有向图）
该顶点的入边的数目。
出度（有向图）
该顶点的出边的数目。
补充：
一个图中，全部顶点的度数之和为所有边数的2倍;
有向图中所有顶点的入度之和等于所有顶点的出度之和；
任意一个无向图一定有偶数个奇点。
子图
设两个图G=（V，E）和G’=(V’,E’),若V’是V的子集,且E’是E的子集,则称G’是G的子图。
路径、简单路径、连通集
对于图G=（V，E），对于顶点a、b，如果存在一些顶点序列x1=a,x2,……,xk=b(k>1)，且（xi,xi+1）∈E，i=1,2…k-1，则称顶点序列x1,x2,……,xk为顶点a到顶点b的一条路径，而路径上边的数目（即k-1）称为该路径的长度。并称顶点集合{x1,x2,……,xk}为一个连通集。
如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径。
回路
起点和终点相同的简单路径称为回路（或环）。
连通
在一个图中，如果从顶点U到顶点V有路径，则称U和V是连通的。
连通图
如果一个无向图中，任意两个顶点之间都是连通的，则称该无向图为连通图。否则称为非连通图。
连通分量
一个无向图的连通分量定义为该图的最大连通子图。
补充：
任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
强连通图
在一个有向图中，对于任意两个顶点U和V，都存在着一条从U到V的有向路径，同时也存在着一条从V到U的有向路径，则称该有向图为强连通图。
强连通分量
一个有向图的强连通分量定义为该图的最大的强连通子图。
补充：
强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。
分类
无向图
边集E（G）中为无向边。
有向图
边集E（G）中为有向边。
带权图
边上带有权的图，也称为网。（又分有向带权图、无向带权图）
完全图
若是无向图，则每两个顶点之间都存在着一条边；若是有向图，则每两个顶点之间都存在着方向相反的两条边。
补充：
一个n个顶点的完全无向图含有n×(n-1)/2条边；
一个n个顶点的完全有向图含有n×(n-1)条边。
稠密图
边数接近完全图的图。
稀疏图
边数远远少于完全图的图。
存储
图型结构的存储分为静态存储和动态存储。
邻接矩阵
邻接矩阵是表示顶点间相邻关系的矩阵。若G=（V，E）是一个具有n个顶点的图，则G的邻接矩阵是如下定义的二维数组a，其规模为n*n。
a[i,j]={1（或权）,（vi,vj）∈E；0（±∞），（vi,vj）∉E}
//第8行将每一个点初始化为无穷大，表示不联通。
//如果图不带权，可以用g[i][j]=0表示不连通。
特点
占用的存储单元数只与顶点数n有关，与边数无关，n*n的二维数组。
方便度数的计算。
容易判断两点之间是否有边相连。
寻找一个点相连的所有边需要一个1到n的循环。
邻接表（用数组+结构体模拟）
方法一
定义二维数组g[101][101]，g[i][0]表示i发出的边的数量，g[i][j]表示i发出的第j条边指向哪个顶点。
这样就可以处理i发出的每条边，也就能找到顶点i指向的顶点。
方法二
特点
适用于点多边少的稀疏图。
（对于有n个点，m条边的稀疏图来说，用邻接矩阵存会开n²的空间；而邻接表则是视边数的多少来开内存大小）
可以快速找到与当前顶点相连的点。
（结构体的next指针比较方便）
判断两点是否相连不如邻接矩阵快速。
（邻接矩阵是看aij的数值，直接O(1)查询即可；邻接表判断起来比较繁琐。）
边集数组
是利用一维数组存储图中所有边的一种图的表示方法。
边集数组由两个一维数组构成，一个存储顶点的信息，另一个存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin），终点下标（end）和权（weight）组成。
前向星
以储存边的方式来存储图。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。
实现
读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序(可以使用基数排序)，前向星就构造完了。
遍历
从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。
为避免重复访问，需要一个状态数组vis[n]，用来存储各顶点的访问状态。如果vis[i]=1，则表示顶点i已经访问过；如果vis[i]=0，则表示顶点i还未访问过。初始化时，各顶点的访问状态均为0。
深度优先遍历(dfs)
广度优先遍历(bfs)
为了实现逐层访问，bfs算法在实现时需要使用一个队列。
补充
AOV网
在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合。
这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系。
子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络”，又称“AOV网”。
在AOV网中，有向边代表子工程（活动）的先后关系，我们把一条有向边起点的活动称为终点活动的前驱活动，同理终点的活动称为起点活动的后继活动。
而只有当一个活动全部的前驱全部都完成之后，这个活动才能进行。
一个AOV网必定是一个有向无环图，即不应该带有回路。否则，会出现先后关系的自相矛盾。
拓扑排序
所谓拓扑排序，就是把AOV网中的所有活动排成一个序列， 使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。
即把有向图上的n个点重新标号为1到n，满足对于任意一条边 (u, v)，都有u<v。
并不是所有的图都能进行拓扑排序，只要图中有环，那么就可以导出矛盾。
因此拓扑排序算法只适用于AOV网（有向无环图，DAG）,有向无环图有很多优美的性质，比如可以在拓扑序上进行DP。
一个AOV网的拓扑序列不一定是唯一的。
实现
我们记录一下每一个点的入度和出度，用一个队列维护当前所有入度为0的点。每次拿出来一个入度为0的点并且将它加到拓扑序中，然后枚举出边更新度数上述两步，重复，直到不存在入度为0的顶点为止。
若完成时队列中的顶点数小于AOV网中的顶点数，则图中有回路，否则此队列中的顶点序列就是一种拓扑序。
可以看出，拓扑排序可以用来判断一个有向图是否有环，因为只有有向无环图才存在拓扑序列。
（在拓扑排序的过程中可以顺带进行DP）
思路
indgr[i]:顶点i的入度；
stack[ ]:栈；
初始化:top=0 (栈顶指针置零)；
将初始状态所有入度为0的顶点压栈；
I=0 (计数器)；
while 栈非空(top>0)
栈顶的顶点v出栈；top-1; 输出v；i++；
for v的每一个后继顶点u
ndgr[u]--;//u的入度减1
if （u的入度变为0） 顶点u入栈
算法结束
代码
欧拉路径（欧拉通路）
如果图中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。
欧拉回路
首尾相接的欧拉路径称为欧拉回路。
判定
由于每一条边都要经过恰好一次，因此对于除了起点和终点之外的任意一个节点，只要进来，一定要出去。
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数（即不存在奇点），且该图只有一个存在边的连通块。
一个无向图存在欧拉路径，当且仅当该图中奇点的数量为0或2，且该图只有一个存在边的连通块；如果存在2个奇点，则此欧拉路径一定是从一个奇点出发，在另一个奇点结束。
一个有向图存在欧拉回路，当且仅当所有点的入度等于出度。
一个混合图存在欧拉回路，当且仅当存在一个对所有无向边定向的方案，使得所有点的入度等于出度。需要用网络流。
求法
我们用 dfs来求出一张图的欧拉回路。
我们给每一条边一个 vis数组代表是否访问过，接下来从一个点出发，遍历所有的边。
直接dfs并且记录的话会有一些问题。
为了解决这个问题，我们在记录答案的时候倒着记录，也就是当我们通过 (u, v) 这条边到达 v 的时候，先把 v dfs 完再加入 (v, u) 这条边。
还有一点需要注意。因为一个点可能被访问多次，一不小心可能会写成 O(n 2 ) 的（因为每次遍历所有的出边）。解决方案就是设一个cur数组，每次直接从上一次访问到的出边继续遍历。
代码
欧拉图
有欧拉回路的图称为欧拉图（Euler Graph）；
有欧拉通路而没有欧拉回路的图称为半欧拉图。
哈密尔顿通路
通过图中每个顶点一次且仅一次的通路。
哈密尔顿回路
通过图中每个顶点一次且仅一次的回路。
求法
一般用搜索解决。
哈密尔顿图
存在哈密尔顿回路的图。
最短路径
所谓最短路，就是把边权看做边的长度，从某个点 S到另一个点 T 的最短路径。
用更加数学化的语言描述就是，对于映射 $ f : V \to R $ ,满足 $ f \left ( S \right ) = 0 $ 且 $ \forall ( x , y , l ) \in E $ , | f ( x ) − f ( y ) | $ \le l $ 的情况下，f(T) 的最大值。
最短路问题
最短路问题（short-path problem）是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。
一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径,（Dijkstra、Bellman-ford、SPFA）；另一类是求图中每一对顶点间的最短路径,（floyed）。
单源最短路——Dijkstra
在所有的边权均为正的情况下，我们可以使用Dijkstra算法求出一个点到所有其它点的最短路径。
我们维护一个集合，表示这个集合内的点最短路径已经确定了。
每次我们从剩下的点中选择当前距离最小的点 u 加入这个集合，然后枚举另一个点 v 进行更新：
$ Dv = min \left ( Dv , Du + W \left ( u , v \right ) \right ) $
实现
设起点为s，dis[ v ]表示从s到v的最短路径，path[ v ]为v的前驱节点，用来输出路径。
1、初始化：
$ dis \left [ v \right ] = + \infty \left ( v \ne s \right ) ; $
$ dis \left [ s \right ] = 0 ; $
$ path \left [ s \right ] = 0 ; $
2、在没有被访问过的点中找一个顶点u使得dis[ u ]是最小的。
3、u标记为已确定最短路径。
4、for与u相连的每个未确定最短路径的顶点v。
优化
第一个是找出当前距离最小的点。这个可以用堆很容易地实现。
第二个是枚举 v，如果我们用邻接表存图，可以降到边数级别。
这样我们就把复杂度降到了 O((n + m) log n)。
单源最短路——Bellman-Ford
简称Ford（福特）算法，另一种求单源最短路的算法，复杂度不如Dijkstra优秀，能够处理存在负边权的情况，但无法处理存在负权回路的情况。
负权回路
存在负权回路的图无法求出最短路径，Bellman-Ford算法可以在有负权回路的情况下输出错误提示。
如果在Bellman-Ford算法的两重循环完成后，还是存在某条边使得： $ dis \left [ u \right ] + w \left [ j \right ] < dis \left [ v \right ] $ ，则存在负权回路。
实现
设s为起点，dis[ v ]即为s到v的最短距离，pre[v]为v前驱。w[ j ]是边j的长度，且j连接u、v。
初始化：
$ dis \left [ v \right ] = + \infty \left ( v \ne s \right ) ; $
$ dis \left [ s \right ] = 0 ; $
$ path \left [ s \right ] = 0 ; $
考虑在上面出现过的松弛操作：
dv = min(dv, du + w(u, v))
由于最短路径只会经过最多 n 个点，因此每一个点的最短路径只会被松弛至多 n − 1 次。
所以我们可以对整张图进行 n − 1 次松弛操作，每次枚举所有的边进行更新。
SPFA
它死了。（因为它的复杂度是错误的）
应用：费用流
Bellman-Ford算法不够优秀，于是我们尝试改进这个算法。
注意到，在进行松弛操作的时候，如果点 u 的距离一直没有发生变化，那么就不需要再枚举这个点的出边进行松弛了。
也就是说我们可以用一个队列保存所有距离发生变化的点， 每次取出一个点进行更新。
（主要思想：初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。）
于是SPFA就诞生了。
但是在最坏情况下它的复杂度和 Bellman-Ford 相同，都是 O(nm)，在正式比赛中，没有哪个出题人会放过它。（因为其复杂度本来就是错的）
多源最短路——Floyed
对于一张图，我们希望求出任意两个点之间的最短路径。
我们用 DP（动态规划） 的思想。设 fi,j,k 表示从 i 到 j，途中仅经过前 k个点的最短路。
由于每一个点在最短路中只会出现一次（不然就出现负环了，不存在最短路），所以可以很写出转移方程：
fi,j,k = min(fi,j,k−1, fi,k,k−1 + fk,j,k−1)
在实际求的过程中，最后一维可以用滚动数组优化掉，所以空间复杂度是 $ O \left ( n^2 \right ) $ 。
代码
注意三层循环的顺序不能颠倒。
初始化
$ d \left [ i \right ] \left [ i \right ] = 0 $ //自己到自己为0；
$ d \left [ i \right ] \left [ i \right ] = 边权 $ //i与j有直接相连的边；
$ d \left [ i \right ] \left [ i \right ] = + \infty $ //i与j无直接相连的边。
// 如果是int数组，采用memset(d, 0x7f, sizeof(d))可全部初始化为一个很大的数
Floyd 传递闭包
有时候，我们需要维护一些有传递性的关系，比如相等，连通等等。（12连通，23连通，则 13连通）
初始条件往往是已知若干个点对具有这些关系，然后让你弄 出来所有的关系。
可以直接把 Floyd 算法做一下调整——
dis[i][j]=dis[i][j]|(dis[i][k]&dis[k][j]);
这个算法叫做传递闭包。
多源最短路——Johnson 重赋权
对于多源最短路，如果我们枚举一个点然后跑堆优化的 Dijkstra，那么复杂度是 O(nm log n) 的，在图比较稀疏的情况下，这个复杂度要优于 Floyd 算法的 O(n 3 )。
但是 Dijkstra 算法要求所有边权均非负。
于是就有了重赋权的技巧。
我们新建一个 0 号点，并且从这个点出发向所有点连一条边 权为 0 的边，然后跑单源最短路。（SPFA 或者 Bellman-Ford）
设距离数组为 h，接下来对于每条边 (u, v)，令 w ′ (u, v) = w(u, v) + h(u) − h(v)。
这样所有的边权就都变成非负了，我们就可以跑 Dijkstra 算法了。
证明
首先由于 h(v) ≤ h(u) + w(u, v)，新图的边权一定非负。
设新图上的最短路径为 d ′，原图上的最短路径为 d。
d ′ (u, v) = min a1,a2,...,ak w ′ (u, a1) + w ′ (a1, a2) + · · · + w ′ (ak, v)
= min a1,a2,...,ak w(u, a1) + (h(u) − h(a1)) + w(a1, a2)+ (h(a2) − h(a1)) + · · · + w(ak, v) + (h(v) − h(ak))
= h(u) − h(v) + min a1,a2,...,ak w(u, a1) + · · · + w(ak, v)
= h(u) − h(v) + d(u, v)
最短路树（最短路图）
所谓最短路树，就是在求完从 S 出发的单源最短路之后，
只保留最短路上的边形成的数据结构。
只需要在求的过程中维护一个pre数组表示这个点的前驱即可。很多最短路的变种都需要用这个算法。
最小生成树
用来解决如何用最小的代价用N-1条边连接N个点的问题。
Prim 算法
类比 Dijkstra 算法，我们维护一个集合 S，表示这个集合中 的生成树已经确定了。
算法流程和Dijkstra一样，唯一的区别是用w(u, v) 去更新 dv 而不是用 du + w(u, v)。
主要思想
Prim算法采用“蓝白点”思想：白点代表已经进入最小生成树的点，蓝点代表未进入最小生成树的点。
Prim算法每次循环都将一个蓝点u变为白点，并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。
这样相当于向生成树中添加了n-1次最小的边，最后得到的一定是最小生成树。
n次循环，每次循环让一个新的点加入生成树，n次循环就能把所有点囊括到其中；每次循环我们都能让一条新的边加入生成树，n-1次循环就能生成一棵含有n个点的树；每次循环我们都取一条最小的边加入生成树，n-1次循环结束后，我们得到的就是一棵最小的生成树。
实现
以第一个点为起点生成最小生成树，min[ v ]表示蓝点v与白点相连的最小边权。
MST表示最小生成树的权值之和。
初始化：
$ min \left [ v \right ] = + \infty \left ( v \ne 1 \right ) ; $
$ min \left [ 1 \right ] = 0 ; $
$ MST = 0 ; $
部分伪代码：
算法结束：
MST即为最小生成树的权值之和
Kruskal 算法
前置知识
并查集算法
并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
合并：把两个不相交的集合合并为一个集合。
查询：查询两个元素是否在同一个集合中。
主要思想
Kruskal算法将一个连通块当做一个集合。
Kruskal首先将所有的边按从小到大顺序排序（快排），并认为每一个点都是孤立的，分属于n个独立的集合。
然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。
直到选取到第n-1条边为止。
因为是求的最小生成树，所以我们用贪心的思路，把所有的边权从小到大排序，然后一条一条尝试加入，用并查集维护连通性。
可以发现这样一定能得到原图的最小生成树。
实现
初始化并查集：
$ father \left [ x \right ] = x $
$ tot = 0 $
将所有边用快排从小到大排序。
计数器 k=0;
结束，tot即为最小生成树的总权值之和。
代码
证明
如果某一条边 (u, v) 不属于最小生成树，那么考虑最小生成树上 连接 u, v 的路径，这上面一定有一条边权不小于 w(u, v) 的边 （因为我们是从小到大枚举的所有边），这样替换后答案一定不会变劣。
优化
路径压缩（O(logn)）+安值合并（O(logn)）→O(αn)（αn在 $ 10^8 $ 数据内不超过4，可视为常数）
Kruskal 重构树
前置知识
dfs（深度优先搜索）
LCA（最近公共祖先）
在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。
LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。
树上倍增
用于求LCA（最近公共祖先）。
倍增的思想是二进制。
首先开一个n×logn的数组，比如fa[n][logn],其中fa[i][j]表示i节点的第2^j个父亲是谁。
然后，我们会发现一个性质：
fa[i][j]=fa[fa[i][j-1]][j-1]
用文字叙述为：i的第2^j个父亲 是i的第2(j-1)个父亲的第2(j-1)个父亲。
这样，本来我们求i的第k个父亲的复杂度是O(k)，现在复杂度变成了O(logk)。
Kruskal 重构树是基于 Kruskal 最小生成树算法的一种算 法，它主要通过将边权转化为点权来实现。
流程
将所有边按照边权排序，设 r(x) 表示 x 所在连通块的根节点。（注意这里要用并查集）
枚举所有的边 (u, v)，若 u, v 不连通，则新建一个点 x，令 x 的权值为 w(u, v)。 连接 (x, r(u)) 和 (x, r(v))。 令 r(u) = r(v) = x。
不断重复以上过程，直到所有点均连通。
性质
这样，我们就得到了一棵有 2n − 1 个节点的二叉树，其中叶节点为原图中的点，其余的点代表原图中的边，并且满足父节点权值大于等于子节点。
它有什么用呢？
求 u, v 之间路径上的最大边权 → 求重构树上 u, v 两个点的 LCA。
只保留边权小于等于 x 的边形成的树 → 重构树上点权小于 等于 x 的点的子树。
Borůvka 算法
前置知识
距离
（x1,y1）（x2,y2）
曼哈顿距离：|x1-x2|+|y1-y2|
切比雪夫距离：max(|x1-x2|,|y1-y2|
欧几里得距离：√[(x1-x2)2+(y1-y2)2]
曼哈顿距离与切比雪夫距离的相互转化
两者之间的关系
我们考虑最简单的情况，在一个二维坐标系中，设原点为(0,0)。
如果用曼哈顿距离表示，则与原点距离为1的点会构成一个边长为2–√2的正方形。
如果用切比雪夫距离表示，则与原点距离为1的点会构成一个边长为2的正方形。
对比这两个图形，我们会发现这两个图形长得差不多，他们应该可以通过某种变换互相转化。
事实上,
将一个点(x,y)的坐标变为(x+y,x−y)后,原坐标系中的曼哈顿距离 =新坐标系中的切比雪夫距离。
将一个点(x,y)的坐标变为(（x+y）/2,（x−y）/2) 后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离。
（注意：切比雪夫距离转曼哈顿距离要再除以二）
用处
切比雪夫距离在计算的时候需要取max，往往不是很好优化，对于一个点，计算其他点到该的距离的复杂度为O(n)。
而曼哈顿距离只有求和以及取绝对值两种运算，我们把坐标排序后可以去掉绝对值的影响，进而用前缀和优化，可以把复杂度降为O(1)。
第三种求最小生成树的算法，虽然比较冷门但是很多题需要用到这个算法。
我们维护当前形成的所有连通块，接下来对于每一个连通块，找到边权最小的出边，然后合并两个连通块。
不断重复这个操作，直到整张图变成一个连通块。
Tarjan算法
Tarjan 算法不是某个特定的算法，而是一群算法。
强连通分量
割点/割边/桥
点双连通分量
边双连通分量
离线 O(n) 求 LCA
此外还有很多 Tarjan 独立/合作创造的算法：
Splay，LCT， 斐波那契堆，斜堆，配对堆，可持久化数据结构，……
有向图——强连通分量
如果对于两个点 u, v，同时存在从 u 到 v 的一条路径和从 v 到 u 的一条路径，那么就称这两个点强连通。
如果一张图的任意两个点均强连通，那么就称这张图为强连通图。
强连通分量指的是一张有向图的极大强连通子图。 （极大≠最大）
Tarjan 算法可以用来找出一张有向图的所有强连通分量。
我们用 dfs的方式来找出一张图的强连通分量。
在 dfs 的过程中，对于 (u, v) 这条边：
若 v 未被访问，则递归进去 dfs 并且用 low[v] 更新 low[u]。
若 v 已经被访问并且在栈中，则直接用 dfn[v] 更新 low[u]。
最后如果 dfn[u]=low[u]，则直接把栈中一直到 u 的所有点 拿出来作为一个强连通分量。
有向图——缩点
跑出来强连通分量之后，我们可以把一个强连通分量看成一 个点。
接下来枚举所有的边，如果是一个强连通分量里的就忽略， 否则连接两个对应的强连通分量。这个操作称为缩点。
缩点后就变成了一张有向无环图，处理连通性问题的时候会方便很多。
无向图——割点
对于一张无向图，我们希望求出它的割点。
无向图的割点定义为删掉这个点之后，连通块数量会发生改变的点。
对于 u 的一个子节点 v，若 dfn[u]≤low[v]，则 u 是割点（因 为 v 无法绕过 u 往上走）。
不过需要注意两点：
根节点不能用这种方法，而是应该看它的子节点数量是否大于等于 2，如果是那么根节点就是割点。
枚举出边的时候要特判掉父子边的情况。
无向图——桥
无向图的桥定义为删掉这条边后，连通块数量会发生改变的边。
和上面的方法几乎一模一样，唯一的区别是判断dfn[u]<low[v]而不是dfn[u]≤low[v]。（如果从 v 出发连 u 都无法 到达，那么 (u, v) 就是一个桥边）
甚至连根节点都不需要特判了。
无向图——点/边双连通分量
如果两个点之间存在两条点互不相交的路径，那么就称这两个点是点双连通的。
如果两个点之间存在两条边互不相交的路径，那么就称这两个点是边双连通的。
其余的定义参考强连通分量。
割点将整张图分成了若干个点双连通分量，并且一个割点可以在多个点双连通分量中。
而桥则把整张图拆成了若干个边双连通分量，并且桥不在任意一个边双连通分量中。
魔改一下强连通分量算法即可。
当然，无向图也可以缩点，不过主要还是可以用来建圆方树。
二分图匹配
前置知识
匹配
在图论中，一个匹配是一个边的集合， 其中任意两条边都没有公共顶点。
最大匹配
一个图所有匹配中，所含匹配边数最多的匹配， 称为这个图的最大匹配。
(最大匹配——匈牙利算法)
完美匹配
如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
二分图
如果一个图的顶点能够被分为两个集合 X, Y，满 足每一个集合内部都没有边相连，那么这张图被称作是一张二分图。
（dfs可以判断一张图是否是二分图）
交替路
从一个未匹配点出发，依次经过非匹配边——匹配 边——非匹配边——……形成的路径叫交替路。
增广路
从一个未匹配点出发，依次经过非匹配边——匹配 边——非匹配边——……——非匹配边，最后到达一个未匹配点形成的路径叫增广路。
注意到，一旦我们找出了一条增广路，将这条路径上所有匹配边和非匹配边取反，就可以让匹配数量+1。
匈牙利算法就是基于这个原理。
假设我们已经得到了一个匹配，希望找到一个更大的匹配。
我们从一个未匹配点出发进行 dfs（深度优先搜索），如果找出了一个增广路， 就代表增广成功，我们找到了一个更大的匹配。
如果增广失败，可以证明此时就是最大匹配。
二分图最大权匹配——KM 算法
现在我们把所有的边都带上权值，希望求出所有最大匹配中权值之和最大的匹配。
我们的思路是给每一个点赋一个“期望值”，也叫作顶标函数 c，对于 (u, v) 这条边来说，只有 c(u) + c(v) = w(u, v) 的时 候，才能被使用。
容易发现，此时的答案就是 ∑c(i)。
初始，我们令左边所有点的 c(u) = maxv w(u, v)，也就是说最理想的情况下，每一个点都被权值最大的出边匹配。
接下来开始增广，每次只找符合要求的边。我们定义只走这些边访问到的子图为相等子图。
如果能够找到增广路就直接增广，否则，就把这次增广访问到的左边的所有点的 c − 1，右边所有点的 c + 1。
经过这样一通操作，我们发现原来的匹配每一条边仍然满足条件。同时由于访问到的点左边比右边多一个（其余的都匹配上了），所以这样会导致总的权值−1。
优化
技巧
最小点覆盖
选取最少的点，使得每一条边的两端至少有一 个点被选中。
二分图的最小点覆盖 = 最大匹配
证明
1.由于最大匹配中的边必须被覆盖，因此匹配中的每一个点对 中都至少有一个被选中。
2.选中这些点后，如果还有边没有被覆盖，则找到一条增广路，矛盾。
最大独立集：选取最多的点，使得任意两个点不相邻。
最大独立集 = 点数-最小点覆盖
证明
1.由于最小点覆盖覆盖了所有边，因此选取剩余的点一定是一个合法的独立集。
2.若存在更大的独立集，则取补集后得到了一个更小的点覆盖，矛盾。
最小边覆盖：选取最少的边，使得每一个点都被覆盖。
最小边覆盖 = 点数-最大匹配
证明
1.先选取所有的匹配边，然后对剩下的每一个点都选择一条和 它相连的边，可以得到一个边覆盖。
2.若存在更小的边覆盖，则因为连通块数量 = 点数-边数，这 个边覆盖在原图上形成了更多的连通块，每一个连通块内选一条边，我们就得到了一个更大的匹配。
最小不相交路径覆盖：一张有向图，用最少的链覆盖所有的点，链之间不能有公共点。
将点和边分别作为二分图的两边，然后跑匹配，最小链覆盖 = 原图点数-最大匹配。
最小可相交路径覆盖：一张有向图，用最少的链覆盖所有的 点，链之间可以有公共点。