图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
树
树是一种数据结构，它是由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
中序遍历
中序遍历左子树、访问根结点、中序遍历右子树
voidinorder(treebt)//中序遍历递归算法{ if(bt) { inorder(bt->lchild); cout<
后序遍历
后序遍历左子树、后序遍历右子树、访问根结点
voidpostorder(treebt)//后序递归算法{ if(bt) { postorder(bt->lchild); postorder(bt->rchild); cout<
已知先序序列和中序序列可唯一确定一棵二叉树；
已知中序序列和后序序列可唯一确定一棵二叉树；
已知先序序列和后序序列不可唯一确定一棵二叉树；
二叉树操作（建树、删除、输出）
普通树转二叉树
由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转换成二叉树进行操作。
通用法则：“左孩子，右兄弟”
建树
删除树
插入一个结点到排序二叉树中
在排序二叉树中查找一个数
扩展二叉树
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用“.”补齐，称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列，要求输出其中序和后序序列。
输入样例：
ABD..EF..G..C..
输出样例：
DBFEGAC
DFGEBCA
二叉树的建立和输出
以二叉链表作存储结构，建立一棵二叉树，并输出该二叉树的先序、中序、后序遍历序列、高度和结点总数。
12##3##
//#为空
123
//先序排列
213
//中序排列
231
//后序排列
2
//高度
3
//结点总数
因为本蒟蒻不太会用指针，所以自己写了一个不带指针的，代码很丑，见谅QwQ
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入：
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出：
1行，表示一棵二叉树的先序。
BADC
BDCA
ABCD
分析
中序为BADC，后序为BDCA，所以A为根结点，B、DC分别为左右子树的中序序列，B、DC分别为左右子树的后序序列。然后再递归处理中序为B，后序为B的子树和中序为DC，后序为DC的子树。
自己用char数组写的代码QwQ
二叉树的前序序列与中序序列
二叉树的后序序列
样例输入：
abcdefg
cbdafeg
样例输出：
cdbfgea
#include #include 关于表达式树，我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如，对于下图的遍历结果如下，它们对应着表达式的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表示不连通。 #include 占用的存储单元数只与顶点数n有关，与边数无关，n*n的二维数组。 方便度数的计算。 容易判断两点之间是否有边相连。 寻找一个点相连的所有边需要一个1到n的循环。 邻接表（用数组+结构体模拟） 方法一 定义二维数组g[101][101]，g[i][0]表示i发出的边的数量，g[i][j]表示i发出的第j条边指向哪个顶点。 这样就可以处理i发出的每条边，也就能找到顶点i指向的顶点。 方法二 #include 适用于点多边少的稀疏图。 （对于有n个点，m条边的稀疏图来说，用邻接矩阵存会开n2的空间；而邻接表则是视边数的多少来开内存大小） 可以快速找到与当前顶点相连的点。 （结构体的next指针比较方便） 判断两点是否相连不如邻接矩阵快速。 （邻接矩阵是看aij的数值，直接O(1)查询即可；邻接表判断起来比较繁琐。） 边集数组 是利用一维数组存储图中所有边的一种图的表示方法。 边集数组由两个一维数组构成，一个存储顶点的信息，另一个存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin），终点下标（end）和权（weight）组成。 前向星 以储存边的方式来存储图。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。 实现 读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序(可以使用基数排序)，前向星就构造完了。 #include 从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。 为避免重复访问，需要一个状态数组vis[n]，用来存储各顶点的访问状态。如果vis[i]=1，则表示顶点i已经访问过；如果vis[i]=0，则表示顶点i还未访问过。初始化时，各顶点的访问状态均为0。 深度优先遍历(dfs) #include 为了实现逐层访问，bfs算法在实现时需要使用一个队列。 补充 //如果是非连通图，主程序做如下修改:intmain(){ ... memset(vis,0,sizeof(vis));//把各个点全扫一遍for(inti=1;i<=n;i++)if(vis[i]==0)dfs(i); ... return0;}AOV网 在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合。 这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系。 子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络”，又称“AOV网”。 在AOV网中，有向边代表子工程（活动）的先后关系，我们把一条有向边起点的活动称为终点活动的前驱活动，同理终点的活动称为起点活动的后继活动。 而只有当一个活动全部的前驱全部都完成之后，这个活动才能进行。 一个AOV网必定是一个有向无环图，即不应该带有回路。否则，会出现先后关系的自相矛盾。 拓扑排序 所谓拓扑排序，就是把AOV网中的所有活动排成一个序列，使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。 即把有向图上的n个点重新标号为1到n，满足对于任意一条边(u,v)，都有u 并不是所有的图都能进行拓扑排序，只要图中有环，那么就可以导出矛盾。 因此拓扑排序算法只适用于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++； forv的每一个后继顶点u ndgr[u]--;//u的入度减1 if（u的入度变为0）顶点u入栈 算法结束 代码 for(inti=1;i<=n;i++) if(d[i]==0)q.push(i); while(!q.empty()){ intnode=q.front(); q.pop(); res[++top]=node; for(inthd=head[node];hd;hd=e[hd].nxt){ d[e[hd].to]--; if(d[e[hd].to]==0) q.push(e[hd].to); } }欧拉路径（欧拉通路） 如果图中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。 欧拉回路 首尾相接的欧拉路径称为欧拉回路。 判定 由于每一条边都要经过恰好一次，因此对于除了起点和终点之外的任意一个节点，只要进来，一定要出去。 一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数（即不存在奇点），且该图只有一个存在边的连通块。 一个无向图存在欧拉路径，当且仅当该图中奇点的数量为0或2，且该图只有一个存在边的连通块；如果存在2个奇点，则此欧拉路径一定是从一个奇点出发，在另一个奇点结束。 一个有向图存在欧拉回路，当且仅当所有点的入度等于出度。 一个混合图存在欧拉回路，当且仅当存在一个对所有无向边定向的方案，使得所有点的入度等于出度。需要用网络流。 求法 我们用dfs来求出一张图的欧拉回路。 我们给每一条边一个vis数组代表是否访问过，接下来从一个点出发，遍历所有的边。 直接dfs并且记录的话会有一些问题。 为了解决这个问题，我们在记录答案的时候倒着记录，也就是当我们通过(u,v)这条边到达v的时候，先把vdfs完再加入(v,u)这条边。 还有一点需要注意。因为一个点可能被访问多次，一不小心可能会写成O(n2)的（因为每次遍历所有的出边）。解决方案就是设一个cur数组，每次直接从上一次访问到的出边继续遍历。 欧拉图 有欧拉回路的图称为欧拉图（EulerGraph）； 有欧拉通路而没有欧拉回路的图称为半欧拉图。 哈密尔顿通路 通过图中每个顶点一次且仅一次的通路。 哈密尔顿回路 通过图中每个顶点一次且仅一次的回路。 一般用搜索解决。 哈密尔顿图 存在哈密尔顿回路的图。 最短路径 所谓最短路，就是把边权看做边的长度，从某个点S到另一个点T的最短路径。 用更加数学化的语言描述就是，对于映射$f:V\toR$,满足$f\left(S\right)=0$且$\forall(x,y,l)\inE$,|f(x)f(y)|$\lel$的情况下，f(T)的最大值。 最短路问题 最短路问题（short-pathproblem）是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。 一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径,（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\nes\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)logn)。 单源最短路——Bellman-Ford 简称Ford（福特）算法，另一种求单源最短路的算法，复杂度不如Dijkstra优秀，能够处理存在负边权的情况，但无法处理存在负权回路的情况。 负权回路 存在负权回路的图无法求出最短路径，Bellman-Ford算法可以在有负权回路的情况下输出错误提示。 如果在Bellman-Ford算法的两重循环完成后，还是存在某条边使得：$dis\left[u\right]+w\left[j\right] if(dis[u]+w[j] 设s为起点，dis[v]即为s到v的最短距离，pre[v]为v前驱。w[j]是边j的长度，且j连接u、v。 初始化： 考虑在上面出现过的松弛操作： dv=min(dv,du+w(u,v)) 由于最短路径只会经过最多n个点，因此每一个点的最短路径只会被松弛至多n1次。 所以我们可以对整张图进行n1次松弛操作，每次枚举所有的边进行更新。 SPFA 它死了。（因为它的复杂度是错误的） 应用：费用流 Bellman-Ford算法不够优秀，于是我们尝试改进这个算法。 注意到，在进行松弛操作的时候，如果点u的距离一直没有发生变化，那么就不需要再枚举这个点的出边进行松弛了。 也就是说我们可以用一个队列保存所有距离发生变化的点，每次取出一个点进行更新。 （主要思想：初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。） 于是SPFA就诞生了。 但是在最坏情况下它的复杂度和Bellman-Ford相同，都是O(nm)，在正式比赛中，没有哪个出题人会放过它。（因为其复杂度本来就是错的） 多源最短路——Floyed 对于一张图，我们希望求出任意两个点之间的最短路径。 我们用DP（动态规划）的思想。设fi,j,k表示从i到j，途中仅经过前k个点的最短路。 由于每一个点在最短路中只会出现一次（不然就出现负环了，不存在最短路），所以可以很写出转移方程： fi,j,k=min(fi,j,k1,fi,k,k1+fk,j,k1) 在实际求的过程中，最后一维可以用滚动数组优化掉，所以空间复杂度是$O\left(n^2\right)$。 for(intk=1;k<=n;k++) for(inti=1;i<=n;i++) for(intj=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);注意三层循环的顺序不能颠倒。 初始化 $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(nmlogn)的，在图比较稀疏的情况下，这个复杂度要优于Floyd算法的O(n3)。 但是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)=mina1,a2,...,akw′(u,a1)+w′(a1,a2)+···+w′(ak,v) =mina1,a2,...,akw(u,a1)+(h(u)h(a1))+w(a1,a2)+(h(a2)h(a1))+···+w(ak,v)+(h(v)h(ak)) =h(u)h(v)+mina1,a2,...,akw(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\ne1\right);$ $min\left[1\right]=0;$ $MST=0;$ 部分伪代码： for(i=1;i<=n;i++) 寻找min[u]最小的蓝点u。 将u标记为白点 MST+=min[u] for与白点u相连的所有蓝点v if(w[u][v] MST即为最小生成树的权值之和 Kruskal算法 并查集算法 并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： 合并：把两个不相交的集合合并为一个集合。 查询：查询两个元素是否在同一个集合中。 Kruskal算法将一个连通块当做一个集合。 Kruskal首先将所有的边按从小到大顺序排序（快排），并认为每一个点都是孤立的，分属于n个独立的集合。 然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。 直到选取到第n-1条边为止。 因为是求的最小生成树，所以我们用贪心的思路，把所有的边权从小到大排序，然后一条一条尝试加入，用并查集维护连通性。 可以发现这样一定能得到原图的最小生成树。 初始化并查集： $father\left[x\right]=x$ $tot=0$ 将所有边用快排从小到大排序。 计数器k=0; for(i=1;i<=M;i++)//遍历所有边 if(这是一条u,v不属于同一集合的边(u,v)(因为已经排序，所以必为最小)){ 合并u,v所在的集合 把边(u,v)加入最小生成树 tot=tot+W(u,v); k++; if(k=n-1)//说明最小生成树已经生成 break; }结束，tot即为最小生成树的总权值之和。 find(intx){ returnx==pa[x]x:pa[x]=find(pa[x])}证明 如果某一条边(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。 不断重复以上过程，直到所有点均连通。 这样，我们就得到了一棵有2n1个节点的二叉树，其中叶节点为原图中的点，其余的点代表原图中的边，并且满足父节点权值大于等于子节点。 它有什么用呢？ 求u,v之间路径上的最大边权→求重构树上u,v两个点的LCA。 只保留边权小于等于x的边形成的树→重构树上点权小于等于x的点的子树。 Borvka算法 距离 （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,xy)后,原坐标系中的曼哈顿距离=新坐标系中的切比雪夫距离。 将一个点(x,y)的坐标变为(（x+y）/2,（xy）/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] 甚至连根节点都不需要特判了。 无向图——点/边双连通分量 如果两个点之间存在两条点互不相交的路径，那么就称这两个点是点双连通的。 如果两个点之间存在两条边互不相交的路径，那么就称这两个点是边双连通的。 其余的定义参考强连通分量。 割点将整张图分成了若干个点双连通分量，并且一个割点可以在多个点双连通分量中。 而桥则把整张图拆成了若干个边双连通分量，并且桥不在任意一个边双连通分量中。 魔改一下强连通分量算法即可。 当然，无向图也可以缩点，不过主要还是可以用来建圆方树。 二分图匹配 匹配 在图论中，一个匹配是一个边的集合，其中任意两条边都没有公共顶点。 最大匹配 一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。 (最大匹配——匈牙利算法) 完美匹配 如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。 二分图 如果一个图的顶点能够被分为两个集合X,Y，满足每一个集合内部都没有边相连，那么这张图被称作是一张二分图。 （dfs可以判断一张图是否是二分图） 交替路 从一个未匹配点出发，依次经过非匹配边——匹配边——非匹配边——……形成的路径叫交替路。 增广路 从一个未匹配点出发，依次经过非匹配边——匹配边——非匹配边——……——非匹配边，最后到达一个未匹配点形成的路径叫增广路。 注意到，一旦我们找出了一条增广路，将这条路径上所有匹配边和非匹配边取反，就可以让匹配数量+1。 匈牙利算法就是基于这个原理。 假设我们已经得到了一个匹配，希望找到一个更大的匹配。 我们从一个未匹配点出发进行dfs（深度优先搜索），如果找出了一个增广路，就代表增广成功，我们找到了一个更大的匹配。 如果增广失败，可以证明此时就是最大匹配。 二分图最大权匹配——KM算法 现在我们把所有的边都带上权值，希望求出所有最大匹配中权值之和最大的匹配。 我们的思路是给每一个点赋一个“期望值”，也叫作顶标函数c，对于(u,v)这条边来说，只有c(u)+c(v)=w(u,v)的时候，才能被使用。 容易发现，此时的答案就是∑c(i)。 初始，我们令左边所有点的c(u)=maxvw(u,v)，也就是说最理想的情况下，每一个点都被权值最大的出边匹配。 接下来开始增广，每次只找符合要求的边。我们定义只走这些边访问到的子图为相等子图。 如果能够找到增广路就直接增广，否则，就把这次增广访问到的左边的所有点的c1，右边所有点的c+1。 经过这样一通操作，我们发现原来的匹配每一条边仍然满足条件。同时由于访问到的点左边比右边多一个（其余的都匹配上了），所以这样会导致总的权值1。 技巧 最小点覆盖 选取最少的点，使得每一条边的两端至少有一个点被选中。 二分图的最小点覆盖=最大匹配 1.由于最大匹配中的边必须被覆盖，因此匹配中的每一个点对中都至少有一个被选中。 2.选中这些点后，如果还有边没有被覆盖，则找到一条增广路，矛盾。 最大独立集：选取最多的点，使得任意两个点不相邻。 最大独立集=点数-最小点覆盖 1.由于最小点覆盖覆盖了所有边，因此选取剩余的点一定是一个合法的独立集。 2.若存在更大的独立集，则取补集后得到了一个更小的点覆盖，矛盾。 最小边覆盖：选取最少的边，使得每一个点都被覆盖。 最小边覆盖=点数-最大匹配 1.先选取所有的匹配边，然后对剩下的每一个点都选择一条和它相连的边，可以得到一个边覆盖。 2.若存在更小的边覆盖，则因为连通块数量=点数-边数，这个边覆盖在原图上形成了更多的连通块，每一个连通块内选一条边，我们就得到了一个更大的匹配。 最小不相交路径覆盖：一张有向图，用最少的链覆盖所有的点，链之间不能有公共点。 将点和边分别作为二分图的两边，然后跑匹配，最小链覆盖=原图点数-最大匹配。 最小可相交路径覆盖：一张有向图，用最少的链覆盖所有的点，链之间可以有公共点。