快上网专注成都网站设计 成都网站制作 成都网站建设
成都网站建设公司服务热线:028-86922220

网站建设知识

十年网站开发经验 + 多家企业客户 + 靠谱的建站团队

量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决

图论

图论

在鄂伦春等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都网站建设、网站建设 网站设计制作定制网站设计,公司网站建设,企业网站建设,高端网站设计,全网整合营销推广,成都外贸网站建设公司,鄂伦春网站建设费用合理。

图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。

树是一种数据结构,它是由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入栈

算法结束

代码

	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);
		}
	}

欧拉路径(欧拉通路)

如果图中的一个路径包括每个边恰好一次,则该路径称为欧拉路径。

欧拉回路

首尾相接的欧拉路径称为欧拉回路。

判定

由于每一条边都要经过恰好一次,因此对于除了起点和终点之外的任意一个节点,只要进来,一定要出去。

一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数(即不存在奇点),且该图只有一个存在边的连通块。

一个无向图存在欧拉路径,当且仅当该图中奇点的数量为0或2,且该图只有一个存在边的连通块;
如果存在2个奇点,则此欧拉路径一定是从一个奇点出发,在另一个奇点结束。

一个有向图存在欧拉回路,当且仅当所有点的入度等于出度。

一个混合图存在欧拉回路,当且仅当存在一个对所有无向边定向的方案,使得所有点的入度等于出度。需要用网络流。

求法

我们用 dfs来求出一张图的欧拉回路。

我们给每一条边一个 vis数组代表是否访问过,接下来从一个点出发,遍历所有的边。

直接dfs并且记录的话会有一些问题。

为了解决这个问题,我们在记录答案的时候倒着记录,也就是当我们通过 (u, v) 这条边到达 v 的时候,先把 v dfs 完再加入 (v, u) 这条边。

还有一点需要注意。因为一个点可能被访问多次,一不小心可能会写成 O(n 2 ) 的(因为每次遍历所有的出边)。解决方案就是设一个cur数组,每次直接从上一次访问到的出边继续遍历。

时间复杂度 O(n + m)。

代码

	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;
		}
	}

欧拉图

有欧拉回路的图称为欧拉图(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。

#include	
#include   
using namespace std;   
const int inf=; 
const int maxn=101;
int f[maxn],a[maxn][maxn],d[maxn],path[maxn];  
int n,start; 
void init(){
	cin>>n>>m>>start;
	int x,y,w;
	for(int i=1;i<=n;i++)
	  	for(int j=1;j<=n;j++){
	  		if(j==i) a[i][j]=0;
	  		else a[i][j]=inf;
	  	}
	for(int i=1;i<=m;i++){        
		cin>>x>>y>>w;
		a[x][y]=w;
		a[y][x]=w;
	}
}
void dijkstra(int s){
	for(int i=1;i<=n;i++){
		d[i]=inf; 
		f[i]=false;  
	}
    d[s]=0;
    for(int i=1;i<=n;i++){
		int mind=inf;  
		int k;//用来记录准备放入集合1的点
		for(int j=1;j<=n;j++)//查找集合2中d[]最小的点
		if((!f[j])&&(d[j]

优化

我们注意到,复杂度主要来源于两个地方。

第一个是找出当前距离最小的点。这个可以用堆很容易地实现。

第二个是枚举 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 ] $ ,则存在负权回路。

if(dis[u]+w[j]

实现

设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 次松弛操作,每次枚举所有的边进行更新。

for(i=1;i<=n-1;i++)
	for(j=1;j<=E;j++)//枚举所有边,而不是枚举点
		if(dis[u]+w[j]

时间复杂度 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 ) $ 。

代码

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]);

注意三层循环的顺序不能颠倒。

初始化

$ 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 ; $

部分伪代码:

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条边为止。

因为是求的最小生成树,所以我们用贪心的思路,把所有的边权从小到大排序,然后一条一条尝试加入,用并查集维护连通性。

可以发现这样一定能得到原图的最小生成树。

时间复杂度$ O \left ( m log m \right ) $ 。

实现

初始化并查集:

$ 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(int x){
	return x==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。

不断重复以上过程,直到所有点均连通。

时间复杂度 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……

并非原创,仅是整理,请见谅


本文题目:图论
当前URL:http://6mz.cn/article/dsoihse.html