大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
图论
在鄂伦春等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都网站建设、网站建设 网站设计制作定制网站设计,公司网站建设,企业网站建设,高端网站设计,全网整合营销推广,成都外贸网站建设公司,鄂伦春网站建设费用合理。
图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。
树
树是一种数据结构,它是由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的子结点,它们又是兄弟结点)。
遍历
树结构解决问题时,按照某种次序获得树中全部结点的信息,这种操作叫作树的遍历。
先序(根)遍历
先访问根结点,再从左到右按照先序思想遍历各棵子树(如,上图先序遍历的结果为)。
后序(根)遍历
先从左到右遍历各棵子树,再访问根结点(如,上图后序遍历的结果为)。
层次遍历
按层次从小到大逐个访问,同一层次按照从左到右的次序(如,上图层次遍历的结果为)。
叶结点遍历
即从左到右遍历所有叶节点(如,上图叶节点遍历的结果为)。
二叉树
二叉树是一种特殊的树型结构,它是度数为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种遍历方法,先(根)序遍历,中(根)序遍历,后(根)序遍历。
先序遍历
若二叉树为空,则空操作,否则:
访问根结点、先序遍历左子树、先序遍历右子树
void preorder(tree bt)//先序递归算法
{
if(bt)
{
cout << bt->data;
preorder(bt->lchild);
preorder(bt->rchild);
}
}
先序遍历此图结果为:
中序遍历
若二叉树为空,则空操作,否则:
中序遍历左子树、访问根结点、中序遍历右子树
void inorder(tree bt)//中序遍历递归算法
{
if(bt)
{
inorder(bt->lchild);
cout << bt->data;
inorder(bt->rchild);
}
}
中序遍历上图结果为:
后序遍历
若二叉树为空,则空操作,否则:
后序遍历左子树、后序遍历右子树、访问根结点
void postorder(tree bt)//后序递归算法
{
if(bt)
{
postorder(bt->lchild);
postorder(bt->rchild);
cout << bt->data;
}
}
后序遍历上图结果为:
已知先序序列和中序序列可唯一确定一棵二叉树;
已知中序序列和后序序列可唯一确定一棵二叉树;
已知先序序列和后序序列不可唯一确定一棵二叉树;
二叉树操作(建树、删除、输出)
普通树转二叉树
由于二叉树是有序的,而且操作和应用更广泛,所以在实际使用时,我们经常把普通树转换成二叉树进行操作。
通用法则:“左孩子,右兄弟”
建树
删除树
插入一个结点到排序二叉树中
在排序二叉树中查找一个数
相关题目
扩展二叉树
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树,所以对二叉树做如下处理,将二叉树的空结点用“.”补齐,称为原二叉树的扩展二叉树,扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列,要求输出其中序和后序序列。
输入样例:
ABD..EF..G..C..
输出样例:
DBFEGAC
DFGEBCA
二叉树的建立和输出
以二叉链表作存储结构,建立一棵二叉树,并输出该二叉树的先序、中序、后序遍历序列、高度和结点总数。
输入样例:
12##3##
//#为空
输出样例:
123
//先序排列
213
//中序排列
231
//后序排列
2
//高度
3
//结点总数
因为本蒟蒻不太会用指针,所以自己写了一个不带指针的,代码很丑,见谅QwQ
#include
#include
#define ll long long
using namespace std;
int top,maxh;
char s;
struct t{
int data,father,lson=0,rson=0,h=0;
//这里的father其实并没有用,但记录一下可以更方便地找到一个点的父节点
}tree[];
void build(int father,bool right){
cin>>s;
if(s=='\n')
return;
if(s!='#'){
++top;
int t=top;
tree[t].father=father;
tree[t].data=s-'0';
tree[t].h=tree[father].h+1;
maxh=max(tree[t].h,maxh);
if(right==1)
tree[father].rson=t;
else
tree[father].lson=t;
build(t,0);
build(t,1);
}
else return;
}
void xian(int now){
cout<
P1030 求先序排列
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度<=8)。
输入:
2行,均为大写字母组成的字符串,表示一棵二叉树的中序与 后序排列。
输出:
1行,表示一棵二叉树的先序。
输入样例:
BADC
BDCA
输出样例:
ABCD
分析
中序为BADC,后序为BDCA,所以A为根结点,B、DC分别为左右子树的中序序列,B、DC分别为左右子树的后序序列。然后再递归处理中序为B,后序为B的子树和中序为DC,后序为DC的子树。
自己用char数组写的代码QwQ
#include
#include
#include
#define ll long long
using namespace std;
char mid[10],post[10];
//mid数组记录中序排列,post数组记录后序排列
//除了打暴力最好不要用string
int z[10],m[10],p[10];
//z数组做中转使用,m数组记录mid数组的内容,p数组记录post数组的每一位在mid数组中的位置
void find(int start,int end,int kai,int jie){
//start和end记录我们正在找的mid数组的范围
//kai(开头)和jie(结尾)记录我们正在找的post数组的范围
if(start>end||kai>jie)return;
//如果开头大于结尾,就返回
if(start==end||kai==jie){
printf("%c",mid[p[jie]]);
return;
}
//如果开头等于结尾,那此节点一定没有儿子,输出当前节点并返回
printf("%c",mid[p[jie]]);
//前面说过后序排列的最后一位就是当前树的根节点,所以p[jie]就是根节点在mid数组中的位置
//开头小于结尾,那就输出当前节点然后再去寻找此节点的左儿子和右儿子
find(start,p[jie]-1,kai,kai+p[jie]-start-1);
//求左子树的范围,然后递归寻找左儿子
find(p[jie]+1,end,kai+p[jie]-start,jie-1);
//求右子树的范围,然后递归寻找右儿子
}
int main(){
scanf("%s%s",mid+1,post+1);
//输入时下标从1开始(主要是因为我比较毛病)
int len=strlen(mid+1);
//输入时下标从1开始那么计算字符串长度时也要加1
for(int i=1;i<=len;i++){
m[i]=mid[i]-'A'+1;
//将每一位转成数字以方便处理(是的,我很毛病)
z[m[i]]=i;
//z数组记录m数组每一位的位置(这一步是为了方便后面记录post数字)
}
for(int i=1;i<=len;i++){
p[i]=z[post[i]-'A'+1];
//记录post数组的每一位在mid数组中的位置
//z:我滴任务完成啦!
}
find(1,len,1,len);
//开始递归
return 0;
}
求后序排列
输入:
二叉树的前序序列与中序序列
输出:
二叉树的后序序列
样例输入:
abcdefg
cbdafeg
样例输出:
cdbfgea
#include
#include
#include
#define ll long long
using namespace std;
char qian[],zhong[];
int q[],z[],a[],cnt=0;
void find(int start,int end){
if(start>end){
return;
}
cnt++;
if(start==end){
cout<>qian>>zhong;
int len=strlen(qian);
for(int i=0;i
因为有小可爱说我的代码在输入时的处理不清楚,所以又写了一个版本QwQ
#include
#include
#include
#define ll long long
using namespace std;
char qian[],zhong[];
int q[],z[],a[],cnt=0;
void find(int start,int end){
// cout<end){
return;
}
cnt++;
if(start==end){
cout<>qian+1>>zhong+1;
scanf("%s%s",qian+1,zhong+1);//这里的输入下标从1开始
int len=strlen(qian+1);
for(int i=1;i<=len;i++){
a[zhong[i]-'a']=i;
}
for(int i=1;i<=len;i++){
z[i]=zhong[i]-'a'+1;
q[i]=a[qian[i]-'a'];
}
find(1,len);
return 0;
}
表达式树
关于表达式树,我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果,如,对于下图的遍历结果如下,它们对应着表达式的3种表示方法。
-+a*b-cd/ef (前缀表示、波兰式)
a+b*(c-d)-e/f (中缀表示)
abcd-*+ef/- (后缀表示、逆波兰式)
哈夫曼树
QwQ,不是很会,那就推荐一篇博客吧。
前置知识
图
如果数据元素集合中的各元素之间存在任意的关系,则此数据结构称为图。
如果将数据元素抽象为顶点(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的有向路径,则称该有向图为强连通图。
强连通分量
一个有向图的强连通分量定义为该图的最大的强连通子图。
补充:
强连通图只有一个强连通分量,即本身,非强连通图有多个强连通分量。
图的连通性判断(用BFS和DFS实现)
分类
无向图
边集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
using namespace std;
double g[101][101];//全为0,不通
int main(){
cin>>n;
//邻接矩阵存储
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>g[i][j];
for(int i=1;i<=n;i++){
int tot=0;
//统计每行数字1,即出度
for(int j=1;j<=n;j++)
if(g[i][j]>0)tot++;
a[i]=tot; //按行统计存储
}
......
return 0;
}
特点
占用的存储单元数只与顶点数n有关,与边数无关,n*n的二维数组。
方便度数的计算。
容易判断两点之间是否有边相连。
寻找一个点相连的所有边需要一个1到n的循环。
邻接表(用数组+结构体模拟)
方法一
定义二维数组g[101][101],g[i][0]表示i发出的边的数量,g[i][j]表示i发出的第j条边指向哪个顶点。
这样就可以处理i发出的每条边,也就能找到顶点i指向的顶点。
方法二
#include
using namespace std;
const int maxn=1001,maxm=;
int head[maxn],num_edge,n,m,u,v;
struct Edge{
int next;//下一条边的编号
int to;//这条边到达的点
}edge[maxm];//结构体变量
void add_edge(int from,int to){
//加入一条从from到to的单向边
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
head[from]=num_edge;
}
int main(){
num_edge=0;
scanf("%d %d",&n,&m);//读入点数和边数
for(int i=1;i<=m;i++){
scanf("%d %d",&u,&v);//u、v之间有一条边
add_edge(u,v);
}
int j,chudu[maxn];
for(int i=0;i
特点
适用于点多边少的稀疏图。
(对于有n个点,m条边的稀疏图来说,用邻接矩阵存会开n²的空间;而邻接表则是视边数的多少来开内存大小)
可以快速找到与当前顶点相连的点。
(结构体的next指针比较方便)
判断两点是否相连不如邻接矩阵快速。
(邻接矩阵是看aij的数值,直接O(1)查询即可;邻接表判断起来比较繁琐。)
边集数组
是利用一维数组存储图中所有边的一种图的表示方法。
边集数组由两个一维数组构成,一个存储顶点的信息,另一个存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin),终点下标(end)和权(weight)组成。
前向星
以储存边的方式来存储图。通常用在点的数目太多,或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外,前向星几乎是完美的。
实现
读入每条边的信息,将边存放在数组中,把数组中的边按照起点顺序排序(可以使用基数排序),前向星就构造完了。
#include
using namespace std;
struct Node{
int v,next;
}E[];
int p[],eid=0;
inline void insert(int u,int v){
eid++;
E[eid].v=v;
E[eid].next=p[u];
p[u]=eid;
}
遍历
从图中某一顶点出发系统地访问图中所有顶点,使每个顶点恰好被访问一次,这种运算操作被称为图的遍历。
为避免重复访问,需要一个状态数组vis[n],用来存储各顶点的访问状态。如果vis[i]=1,则表示顶点i已经访问过;如果vis[i]=0,则表示顶点i还未访问过。初始化时,各顶点的访问状态均为0。
深度优先遍历(dfs)
#include
using namespace std;
int n,m;
int a[100][100];
int vis[100];//标记数组
void dfs(int u){
cout<<"V"<>n; //邻接矩阵存储
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
dfs(1);//选定V1开始dfs遍历。
return 0;
}
广度优先遍历(bfs)
为了实现逐层访问,bfs算法在实现时需要使用一个队列。
补充
//如果是非连通图,主程序做如下修改:
int main(){
...
memset(vis,0,sizeof(vis));
//把各个点全扫一遍
for(int i=1;i<=n;i++)
if(vis[i]==0)dfs(i);
...
return 0;
}
AOV网
在日常生活中,一项大的工程可以看作是由若干个子工程(这些子工程称为“活动”)组成的集合。
这些子工程(活动)之间必定存在一些先后关系,即某些子工程(活动)必须在其它一些子工程(活动)完成之后才能开始,我们可以用有向图来形象地表示这些子工程(活动)之间的先后关系。
子工程(活动)为顶点,子工程(活动)之间的先后关系为有向边,这种有向图称为“顶点活动网络”,又称“AOV网”。
在AOV网中,有向边代表子工程(活动)的先后关系,我们把一条有向边起点的活动称为终点活动的前驱活动,同理终点的活动称为起点活动的后继活动。
而只有当一个活动全部的前驱全部都完成之后,这个活动才能进行。
一个AOV网必定是一个有向无环图,即不应该带有回路。否则,会出现先后关系的自相矛盾。
拓扑排序
所谓拓扑排序,就是把AOV网中的所有活动排成一个序列, 使得每个活动的所有前驱活动都排在该活动的前面,这个过程称为“拓扑排序”,所得到的活动序列称为“拓扑序列”。
即把有向图上的n个点重新标号为1到n,满足对于任意一条边 (u, v),都有u 并不是所有的图都能进行拓扑排序,只要图中有环,那么就可以导出矛盾。 因此拓扑排序算法只适用于AOV网(有向无环图,DAG),有向无环图有很多优美的性质,比如可以在拓扑序上进行DP。 一个AOV网的拓扑序列不一定是唯一的。 实现 我们记录一下每一个点的入度和出度,用一个队列维护当前所有入度为0的点。每次拿出来一个入度为0的点并且将它加到拓扑序中,然后枚举出边更新度数上述两步,重复,直到不存在入度为0的顶点为止。 若完成时队列中的顶点数小于AOV网中的顶点数,则图中有回路,否则此队列中的顶点序列就是一种拓扑序。 可以看出,拓扑排序可以用来判断一个有向图是否有环,因为只有有向无环图才存在拓扑序列。 时间复杂度O(n+m)。 (在拓扑排序的过程中可以顺带进行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,且该图只有一个存在边的连通块; 一个有向图存在欧拉回路,当且仅当所有点的入度等于出度。 一个混合图存在欧拉回路,当且仅当存在一个对所有无向边定向的方案,使得所有点的入度等于出度。需要用网络流。 求法 我们用 dfs来求出一张图的欧拉回路。 我们给每一条边一个 vis数组代表是否访问过,接下来从一个点出发,遍历所有的边。 直接dfs并且记录的话会有一些问题。 为了解决这个问题,我们在记录答案的时候倒着记录,也就是当我们通过 (u, v) 这条边到达 v 的时候,先把 v dfs 完再加入 (v, u) 这条边。 还有一点需要注意。因为一个点可能被访问多次,一不小心可能会写成 O(n 2 ) 的(因为每次遍历所有的出边)。解决方案就是设一个cur数组,每次直接从上一次访问到的出边继续遍历。 时间复杂度 O(n + m)。 代码 欧拉图 有欧拉回路的图称为欧拉图(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 ) $ 直接这样做时间复杂度是 $ O \left ( n^2 \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 次松弛操作,每次枚举所有的边进行更新。 时间复杂度 O(nm)。 SPFA 它死了。(因为它的复杂度是错误的) 应用:费用流 Bellman-Ford算法不够优秀,于是我们尝试改进这个算法。 注意到,在进行松弛操作的时候,如果点 u 的距离一直没有发生变化,那么就不需要再枚举这个点的出边进行松弛了。 也就是说我们可以用一个队列保存所有距离发生变化的点, 每次取出一个点进行更新。 (主要思想:初始时将起点加入队列。每次从队列中取出一个元素,并对所有与它相邻的点进行修改,若某个相邻的点修改成功,则将其入队。直到队列为空时算法结束。) 于是SPFA就诞生了。 如果图是随机的,SPFA的期望时间复杂度约为 O(2m),比之前提到的任何一个算法都优秀,而且还可以有负权。 但是在最坏情况下它的复杂度和 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^3 \right ) $ 。 在实际求的过程中,最后一维可以用滚动数组优化掉,所以空间复杂度是 $ 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)。 时间复杂度 $ O \left ( n^2 \right ) $ ,同样可以用堆优化。 主要思想 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条边为止。 因为是求的最小生成树,所以我们用贪心的思路,把所有的边权从小到大排序,然后一条一条尝试加入,用并查集维护连通性。 可以发现这样一定能得到原图的最小生成树。 时间复杂度$ O \left ( m log m \right ) $ 。 实现 初始化并查集: $ 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。 不断重复以上过程,直到所有点均连通。 时间复杂度 O(m log m)。 性质 这样,我们就得到了一棵有 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)。 第三种求最小生成树的算法,虽然比较冷门但是很多题需要用到这个算法。 我们维护当前形成的所有连通块,接下来对于每一个连通块,找到边权最小的出边,然后合并两个连通块。 不断重复这个操作,直到整张图变成一个连通块。 由于每次操作连通块数量至少减半,所以时间复杂度最坏为 O((n + m) log n),随机图的话复杂度可以降到 O(n + m)。 Tarjan算法 Tarjan 算法不是某个特定的算法,而是一群算法。 强连通分量 割点/割边/桥 点双连通分量 边双连通分量 离线 O(n) 求 LCA 此外还有很多 Tarjan 独立/合作创造的算法: Splay,LCT, 斐波那契堆,斜堆,配对堆,可持久化数据结构,…… 有向图——强连通分量 如果对于两个点 u, v,同时存在从 u 到 v 的一条路径和从 v 到 u 的一条路径,那么就称这两个点强连通。 如果一张图的任意两个点均强连通,那么就称这张图为强连通图。 强连通分量指的是一张有向图的极大强连通子图。 (极大≠最大) Tarjan 算法可以用来找出一张有向图的所有强连通分量。 我们用 dfs的方式来找出一张图的强连通分量。 建出 dfs 树,记录一下每一个节点的时间戳(dfn),然后我们考虑强连通分量应该满足什么条件。 我们可以再记录一个 low 数组,表示每一个点能够到达的最小的时间戳,如果一个点的 dfn=low,那么这个点下方就形成了一个强连通分量。 在 dfs 的过程中,对于 (u, v) 这条边: 若 v 未被访问,则递归进去 dfs 并且用 low[v] 更新 low[u]。 若 v 已经被访问并且在栈中,则直接用 dfn[v] 更新 low[u]。 最后如果 dfn[u]=low[u],则直接把栈中一直到 u 的所有点 拿出来作为一个强连通分量。 时间复杂度 O(n)。 有向图——缩点 跑出来强连通分量之后,我们可以把一个强连通分量看成一 个点。 接下来枚举所有的边,如果是一个强连通分量里的就忽略, 否则连接两个对应的强连通分量。这个操作称为缩点。 缩点后就变成了一张有向无环图,处理连通性问题的时候会方便很多。 无向图——割点 对于一张无向图,我们希望求出它的割点。 无向图的割点定义为删掉这个点之后,连通块数量会发生改变的点。 类比上面,我们还是记录一下 dfn(时间戳)和 low。 对于 u 的一个子节点 v,若 dfn[u]≤low[v],则 u 是割点(因 为 v 无法绕过 u 往上走)。 不过需要注意两点: 根节点不能用这种方法,而是应该看它的子节点数量是否大于等于 2,如果是那么根节点就是割点。 枚举出边的时候要特判掉父子边的情况。 无向图——桥 无向图的桥定义为删掉这条边后,连通块数量会发生改变的边。 和上面的方法几乎一模一样,唯一的区别是判断dfn[u] 甚至连根节点都不需要特判了。 无向图——点/边双连通分量 如果两个点之间存在两条点互不相交的路径,那么就称这两个点是点双连通的。 如果两个点之间存在两条边互不相交的路径,那么就称这两个点是边双连通的。 其余的定义参考强连通分量。 割点将整张图分成了若干个点双连通分量,并且一个割点可以在多个点双连通分量中。 而桥则把整张图拆成了若干个边双连通分量,并且桥不在任意一个边双连通分量中。 魔改一下强连通分量算法即可。 当然,无向图也可以缩点,不过主要还是可以用来建圆方树。 二分图匹配 前置知识 匹配 在图论中,一个匹配是一个边的集合, 其中任意两条边都没有公共顶点。 最大匹配 一个图所有匹配中,所含匹配边数最多的匹配, 称为这个图的最大匹配。 如果要求一般图的最大匹配,需要用 O(n3) 的带花树,至少 是 NOI+ 的算法。在联赛阶段,我们一般只关注二分图的匹配问题。 (最大匹配——匈牙利算法) 完美匹配 如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。 二分图 如果一个图的顶点能够被分为两个集合 X, Y,满 足每一个集合内部都没有边相连,那么这张图被称作是一张二分图。 (dfs可以判断一张图是否是二分图) 交替路 从一个未匹配点出发,依次经过非匹配边——匹配 边——非匹配边——……形成的路径叫交替路。 增广路 从一个未匹配点出发,依次经过非匹配边——匹配 边——非匹配边——……——非匹配边,最后到达一个未匹配点形成的路径叫增广路。 注意到,一旦我们找出了一条增广路,将这条路径上所有匹配边和非匹配边取反,就可以让匹配数量+1。 匈牙利算法就是基于这个原理。 假设我们已经得到了一个匹配,希望找到一个更大的匹配。 我们从一个未匹配点出发进行 dfs(深度优先搜索),如果找出了一个增广路, 就代表增广成功,我们找到了一个更大的匹配。 如果增广失败,可以证明此时就是最大匹配。 由于每个点只会被增广一次,所以时间复杂度是 O(n(n + m))。 二分图最大权匹配——KM 算法 现在我们把所有的边都带上权值,希望求出所有最大匹配中权值之和最大的匹配。 我们的思路是给每一个点赋一个“期望值”,也叫作顶标函数 c,对于 (u, v) 这条边来说,只有 c(u) + c(v) = w(u, v) 的时 候,才能被使用。 容易发现,此时的答案就是 ∑c(i)。 初始,我们令左边所有点的 c(u) = maxv w(u, v),也就是说最理想的情况下,每一个点都被权值最大的出边匹配。 接下来开始增广,每次只找符合要求的边。我们定义只走这些边访问到的子图为相等子图。 如果能够找到增广路就直接增广,否则,就把这次增广访问到的左边的所有点的 c − 1,右边所有点的 c + 1。 经过这样一通操作,我们发现原来的匹配每一条边仍然满足条件。同时由于访问到的点左边比右边多一个(其余的都匹配上了),所以这样会导致总的权值−1。 接下来再尝试进行增广,重复上述过程。直接这样做时间复 杂度是 O(n 3 c) 的。(进行 n 次增广,每次修改 c 次顶标,访问所有 n 2 条边) 优化 由于修改顶标的目标是让相等子图变大,因此可以每次加减 一个最小差值 delta。这样每次增广只会被修改最多 n 次顶标,时间复杂度降到 O(n 4 )。 注意到每次重新进行 dfs(深度优先搜索) 太不优秀了,可以直接进行 bfs, 每次修改完顶标之后接着上一次做。时间复杂度降到 O(n 3 )。 技巧 最小点覆盖 选取最少的点,使得每一条边的两端至少有一 个点被选中。 二分图的最小点覆盖 = 最大匹配 证明 1.由于最大匹配中的边必须被覆盖,因此匹配中的每一个点对 中都至少有一个被选中。 2.选中这些点后,如果还有边没有被覆盖,则找到一条增广路,矛盾。 最大独立集:选取最多的点,使得任意两个点不相邻。 最大独立集 = 点数-最小点覆盖 证明 1.由于最小点覆盖覆盖了所有边,因此选取剩余的点一定是一个合法的独立集。 2.若存在更大的独立集,则取补集后得到了一个更小的点覆盖,矛盾。 最小边覆盖:选取最少的边,使得每一个点都被覆盖。 最小边覆盖 = 点数-最大匹配 证明 1.先选取所有的匹配边,然后对剩下的每一个点都选择一条和 它相连的边,可以得到一个边覆盖。 2.若存在更小的边覆盖,则因为连通块数量 = 点数-边数,这 个边覆盖在原图上形成了更多的连通块,每一个连通块内选一条边,我们就得到了一个更大的匹配。 最小不相交路径覆盖:一张有向图,用最少的链覆盖所有的点,链之间不能有公共点。 将点和边分别作为二分图的两边,然后跑匹配,最小链覆盖 = 原图点数-最大匹配。 最小可相交路径覆盖:一张有向图,用最少的链覆盖所有的 点,链之间可以有公共点。 先跑一遍传递闭包,然后变成最小不相交路径覆盖。 补充 小黄鸭调试法 当你的代码出现问题的时候, 将小黄鸭想象成你的同学, 将你的代码一行一行地讲给它, 也许讲到一半你就知道问题出在哪了。 不要定义以下变量名 next,abs,x1,y1,size…… 并非原创,仅是整理,请见谅 for(int i=1;i<=n;i++)
if(d[i]==0)q.push(i);
while(!q.empty()){
int node=q.front();
q.pop();
res[++top]=node;
for(int hd=head[node];hd;hd=e[hd].nxt){
d[e[hd].to]--;
if(d[e[hd].to]==0)
q.push(e[hd].to);
}
}
如果存在2个奇点,则此欧拉路径一定是从一个奇点出发,在另一个奇点结束。 void dfs(int x)
{
for(int&hd=head[x];hd;hd=e[hd].nxt)
{
if(flag[hd>>1])continue;
flag[hd>>1]=1;
dfs(e[hd].to);
a[++top]=x;
}
}
#include
if(dis[u]+w[j]
for(i=1;i<=n-1;i++)
for(j=1;j<=E;j++)//枚举所有边,而不是枚举点
if(dis[u]+w[j]
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for (i = 1; i<= n; i++)
寻找min[u]最小的蓝点u。
将u标记为白点
MST+=min[u]
for 与白点u相连的所有蓝点v
if (w[u][v]
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;
}
find(int x){
return x==pa[x]?x:pa[x]=find(pa[x])
}
名称栏目:图论
浏览路径:http://dzwzjz.com/article/dsoihse.html