图论相关算法

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,图 论,（Elementary Graph Algorithms,）,1,图的定义,图是由顶点集合以及顶点间的关系的集合组成的一种关系的数学表示,G = （V，E）,其中顶点是由有穷非空集合,顶点之间的关系（边）是有穷集合,Path (x , y),表示从x到y的一条单向通路，它是有方向的,2,图的分类,有向图,：,图中的边是有方向的。E (x ,y) 和E ( y ,x)表示的边不同,无向图,：图中的边是没有方向的。,完全图,：n个顶点的图两两连边，即有 n(n-1)/2条边，则此图为n的完全图。 用K n表示,3,图的一些概念,邻接顶点：,如果(u ,v),E(G),则称u与v互为邻接顶点,子图,：设有两个图G(V,E)和G(V,E)，若V,V 且E E，则称图G是图G的子图,权,：某些图的边上标有相关的数字，称为该边的权值,4,顶点的度,一个顶点V的度是与它相连边的条数，记为Deg(V).,顶点的入度,一个顶点V的入度是以它为终点有向边的条数，记为InDeg(V),顶点的出度,一个顶点V的入度是以它为起点有向边的条数，记为OutDeg(V),路径,在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 Vp1, Vp2, , Vpm，到达顶点Vj。则称顶点序列 (Vi Vp1 Vp2 . Vpm Vj) 为从顶点Vi 到顶点 Vj 的路径。它经过的边(Vi, Vp1)、(Vp1, Vp2)、.、(Vpm, Vj) 应是属于E的边。,5,图的存储表示邻接矩阵(Adjacency Matrix),设图G=(V,E)是一个有N个顶点的图，图的邻接矩阵是一个二维数组G.edgeNN,定义：,G.edgeij=,1 If (i,j) E(G),0 otherwise,6,0,2,1,3,G.edgeij=,0 1 0,0 1,0 0 0,0,1,2,G.edgeij=,0 1 1 1,1 0 0 0,1 0 0 1,1 0 1 0,无向图的临界矩阵是对称的,有向图的邻接矩阵往往是不对称的,7,图的存储表示邻接表(Adjacency List),0,2,1,3,0,1,0,0,2,3,3,2,0,1,2,3,Data adj dest link dest link dest link,同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边，结点中另一个顶点的下表dest和指针link,8,图论相关算法,9,广度优先搜索,通常用队列(先进先出,FIFO)实现,Q=起点s; 标记s为己访问;,while (Q非空) ,取Q队首元素u; u出队;,所有与u相邻且未被访问的点进入队列;,标记u为已访问;,10,广度优先搜索,由BFS得到的路径是原图中从S到T的边数最少的路径,广度优先搜索树不唯一,11,广度优先搜索的例子,0,1,2,5,4,3,6,7,8,0,1,2,5,4,3,6,7,8,0,1,2,5,4,3,6,7,8,0 1 2,1 1 2,2 4 3,12,t = 0;,void,BFS(,int,s ),/ 从 s 开始遍历,int,queuemaxn, tail, head;,head = tail = 0;,queuehead = s; depths = 0;,times = t+; visits =,true,;,while,( head = tail ),/ queue not empty,int,curr = queuehead+;,int,i;,for,(i = 0; i n; i+),if,( adjcurri & !visiti ),visiti = true;,depthi = depthcurr + 1;,timei = t+;,queue+tail = i;,13,深度优先搜索,相关概念,递归实现,结点颜色：,白色（开始），灰色（发现），黑色（结束）,一个结点总是从白色变为灰色，再变为黑色,当所有点都变为黑色时，遍历结束,时间戳(timestamp): du表示一个结点开始被访问的时间，fu表示一个结点结束访问的时间,14,深度优先搜索,int timestamp = 0;,dfs(int p) ,timestamp = timestamp + 1;,colp = GREY;,dp = timestamp;,for (每个与p相邻的点i),if (coli = WHITE) dfs(i);,timestamp = timestamp + 1;,fp = timestamp;,colp = BLACK;,15,16,深度优先搜索,每个顶点的du fu,DFS中，v是u的子孙, dudvfv=2）的标号的GCD为1,17,深度优先搜索,割点与割边,如果从图中删去某点和与该点相关联的边后，图不再连通，那么这个点叫做割点(cut point)。,如果从图中删去某条边后，图不再连通，那么这条边叫做割边或桥(bridge)。,18,关节点：图中的关节点指这样一个顶点，如果删除它，图就会被分割成至少两个分离的子图。关节点也称作分离顶点或,割点,。,0,1,2,3,4,5,6,7,8,9,10,11,12,顶点0、4、5、6、7和11为关节点。,19,割点、割边以及连通分量,时间戳：dfni表示结点i是第dfni个被访问到的结点。有的时候我们 还要记录某个结点被遍历并检查完毕的时间。,void dfs(v),dfnv=+times;,/记录访问结点的时间戳,visitv=1;,for 寻找一个v的相邻节点u,if (visitu=0)then,DFS(u);,20,L,M,A,B,C,F,I,D,G,J,E,H,K,A,B,L,F,M,J,C,H,K,G,I,D,E,连通图G,G的深度优先生成树,21,树边：深度优先搜索树中的实线表示树边，在DFS过程中，从v点访问u点时，若u没有被访问过，则边(v,u)为树边。,回边：深度优先搜索树中的虚线表示回边，在DFS过程中，从v点访问u点时，若u点已经访问过，则边(v,u)为回边。,A,B,L,F,M,J,C,H,K,G,I,D,E,22,由深度优先生成树可得出两类关节点的特性：,(1) 若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。因为图中不存在联结不同子树中顶点的边，因此，若删去根顶点，生成树便变成生成森林。如上图中的顶点A。,(2) 若生成树中某个非叶子顶点v，它的子树中的任一结点均没有指向v的祖先的回边，则v为关节点。因为，若删去v，则其子树和图的其他部分就被分割开来。如上图中的顶点B、D和G。,23,我们在DFS的基础上增加一个low数组，lowi用来记录i及i的子孙相连的辈分最高的祖先的访问时间戳。,lowv=min(dfnv,loww,dfnk);,w是顶点v在深度优先树上的孩子结点；,k是顶点v在深度优先树上由回边联结的祖先结点；,24,当lowj=dfnv,表明w及其子孙均无指向v的祖先的回边，则该顶点v必为关节点。,具体算法如下：,25,void dfs(int v),int i,w,cnum=0; /cnum表示孩子个数,times+;,visitv=1;,dfnv=lowv=times; /记录时间戳,for(i=0;i=dfnv)/不为根若loww=dfnv)，则为关节点,flagv=1;,else if(v!=w) /w已经访问过了，说明从v到w有一条回边，w是v的祖先,lowv=min(lowv,dfnw);,26,桥：图中的桥（bridge）是一条边，如果删除这条边，将把连通图分离成两个断开的子图。无桥的图称作边连通图（edge-connected graph）。,0,1,2,3,4,5,6,7,8,9,10,11,12,这个图不是边连通图。边0-5、6-7和11-12（带阴影）为桥。,27,在任何DFS树中，当且仅当不存在回边连通w的子孙与w的祖先时，树边v-w是一座桥。,与割点类似的，我们定义low和dfn。父子边e=uv ，当且仅当lowv dfnu的时候，e是割边。,28,有向图的强连通分量,在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。,下图中，子图1,2,3,4为一个强连通分量，因为顶点1,2,3,4两两可达。5,6也分别是两个强连通分量。,29,求有向图的强连通分量一般采用Kosaraju算法或Tarjan算法，两者的时间复杂度都是O(n+m),。下面着重介绍一下Tarjan算法。,Tarjan算法,Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。dfs时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。,30,我们仍然定义dfni为节点i搜索的次序编号(时间戳)，lowi为i或i的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出:,当dfn(u)=low(u)时，以u为根的搜索子树上的所有节点构成一个强连通分量。,31,void tarjan(int i),int j;,dfni=lowi=+times;,/ 为节点u设定次序编号和Low初值,instacki=true;,Stack+Stop=i; /,将节点u压入栈中,for (edge *e=Vi;e;e=e-next),j=e-t;,if (!dfnj),tarjan(j);,if (lowjlowi),lowi=lowj;,else if (instackj & dfnjlowi),lowi=dfnj;,if (dfni=lowi),/ 如果节点i是强连通分量的根,Bcnt+;,do,j=StackStop-;,instackj=false;,Belongj=Bcnt;,while (j!=i);,void solve(),int i;,Stop=Bcnt= times =0;,memset(dfn,0,sizeof(dfn);,for (i=1;i=n;i+),if (!dfni),tarjan(i);,32,从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，dfn6=low6=4，找到了一个强连通分量。退栈到u=v为止，6为一个强连通分量。,33,返回节点5，发现dfn5=low5=3，退栈后5为一个强连通分量。,34,返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4存在向节点1的回边，节点1还在栈中，所以low4=dfn1=1。节点6已经出栈，不再访问6，返回3，(3,4)为树边，所以low3=low4=1。,35,继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以low2=4。返回1后，发现DFN1=LOW1，把栈中节点全部取出，组成一个连通分量1,3,4,2。,至此，算法结束。经过该算法，求出了图中全部的三个强连通分量1,3,4,2,5,6。,36,Kosaraju算法,Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。kosaraju算法的步骤如下：,(1)在有向图G上，从某个顶点出发进行DFS，并按其所有邻接点的搜索都完成(即退出DFS函数)的顺序将顶点排列起来。,37,Kosaraju算法,Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。kosaraju算法的步骤如下：,(2)在有向图G上，从最后完成搜索的顶点出发，在图G的逆图G上进行DFS，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续做逆图中的DFS，直至有向图中的所有顶点都被访问到为止。每一次调用DFS作逆图中的遍历所访问到的顶点集便是有向图G中的一个强连通分量。,38,memset(visit,false,sizeof(visit);,cnt=0;,for(i=1;i=0;i-),if(!visitorderi),ans+;,dfsn(orderi);,void dfs(int pos) /正向DFS,int i,j;,visitpos=true;,for(i=0;iadjpos.size();i+),j=adjposi;,if(!visitj),dfs(j);,ordercnt+=pos; /记录结点结束dfs的时间顺序,void dfsn(int pos) /逆向DFS,int i,j;,visitpos=true;,idpos=ans; /求出连通分量,for(i=0;iadjnpos.size();i+),j=adjnposi;,if(!visitj),dfsn(j);,39,拓扑排序,图的结点存在一个拓扑序：如果图中有边(u，v)，则u必定排在v的前面,拓扑排序在有向无环图(DAG)上进行,拓扑序列不一定唯一,40,拓扑排序,利用DFS，当节点u已经扩展完成，将标记颜色置为黑时，将u加入已排序列的顶部，搜索完成时，节点序列为拓扑序,经过拓扑排序的顶点以与其完成时刻相反的顺序出现,41,拓扑排序,算法,(1) 计算每个点的入度，入度为0的点加入队列Q,(2) 从Q中取出一个点p，输出,(3) 所有与p相邻的点的入度减1。如果新得到了入度为0的点，则加入队列Q。,(4) 转步骤(2), 直到所有点都输出完毕,如果在执行过程中发现找不到入度为0的点, 说明图中存在环,42,拓扑排序,1 3 2 4 5 6 7 8 (不唯一),如何生成最小字典序的拓扑序列？,可以使用最小堆维护当前入度为0的节点,2,1,3,4,8,7,5,6,43,最小生成树,生成树：由G的n-1条边构成的无环的子图，这些边的集合成为生成树。,最小生成树：所有生成树中权值最小的一个边集T为最小生成树，确定树T的问题成为最小生成树问题。,prim算法,kruskal算法,44,prim算法,任取一个顶点加入生成树；,在那些一个端点在生成树里，另一个端点不在生成树里的边中，取权最小的边，将它和另一个端点加进生成树。,重复上一步骤，直到所有的顶点都进入了生成树为止。,45,46,int prim(int s)/s为初始加入的点,int i,j,sum=0;,for(i=1;i=n;i+),closesti=mapsi;,useds=1;,int now;,for(i=1;in;i+),int min=INT_MAX;,for(j=1;j=n;j+),if(!usedj&closestjmin),min=closestj;,now=j;,sum+=min;,usednow=1,for(j=1;j=n;j+),if(mapnowj&mapnowjclosestj),closestj=mapnowj;,return sum;,时间复杂度为O(n2)。,(用堆维护最小优先级队列可以达到,O(vlogv+elogv),有兴趣的同学可以自己实现),47,Kruskal,算法,对所有边从小到大排序；,依次试探将边和它的端点加入生成树，如果加入此边后不产生圈，则将边和它的端点加入生成树；否则，将它删去；,直到生成树中有了n-1条边，即告终止。,算法的时间复杂度O(eloge),48,49,kruskal,算法实现的数据结构,一维数组，将所有边按从小到大的顺序存在数组里面,并查集,先把每一个对象看作是一个单元素集合，然后按一定顺序将相关联的元素所在的集合合并。能够完成这种功能的集合就是并查集。,对于并查集来说，每个集合用一棵树表示。,它支持以下操作：,Union (Root1, Root2) /合并两个集合；,getRoot(x) /搜索操作（搜索编号为x所在树的根）。,树的每一个结点有一个指向其父结点的指针。,50,并查集的处理过程,51,并查集的实现,int rootMAXN; /定义根数组，记录每个节点的父亲节点,void init() /函数功能:初始化,for(i=1;i=N;i+)rooti=i; /初始每个节点的根节点为自己,int getRoot(int u) /函数功能：取u的根节点，并压缩路径,if(rootu!=u),rootu=getRoot(rootu);,return rootu;,void union(int u,int v) /函数功能：合并两个节点,int a=getRoot(u),b=getRoot(v);,roota=b;,52,kruskal,的实现,init(); /初始化,sort(.)/按权值对边进行排序,for 每条边 (u,v)E,int r_1=getRoot(u),r_2=getRoot(v);,if(r_1 != r_2),union(u,v);,53,欧拉路,欧拉路：经过图中每条边恰好一次的路,欧拉回路：起点和终点相同的欧拉路,54,欧拉路,无向图存在欧拉路的条件,如果图连通，且所有的点都是偶数度，则有欧拉回路。,如果图连通，且恰有两点是奇数度，则有欧拉路。且欧拉路的起止点为这两个奇数度点。,对重边、自环的情况仍适用。,55,欧拉路,有向图存在欧拉路的条件,如果图连通，且每个点的入度等于出度，则存在欧拉回路。,如果图连通，且恰有一点u的出度比入度大1，另有一点v的出度比入度小1，其余的出度等于出度，则存在欧拉路，起点为u，终点为v。,对重边、自环的情况仍适用。,56,欧拉路,套圈算法,void Euler(int start) ,for (int i = 1; i = E; i +) ,if (!visiti & from = start) ,visiti = 1;,Euler(to);,path+ top = i;,倒序path为欧拉路,57,欧拉路,例题：,给定一组单词，问这些单词能否连成一串，使得前面一个单词的最后一个字母和后面一个单词的第一个字母相同。,58,欧拉路,Sample Input,6,aloha,arachnid,dog,gopher,rat,tiger,3,oak,maple,elm,Sample Output,aloha.arachnid.dog.gopher.rat.tiger,*,59,欧拉路,解法：,先判断连通性,每个单词相当于在首字母和尾字母之间连一条边,得到一个最多26个点的有向图,求欧拉路,60,汉密尔顿路,汉密尔顿路：经过图中每个点恰好一次的路,汉密尔顿回路：起点和终点相同的汉密尔顿路,常见方法：状态压缩DP,61,汉密尔顿路,对于点数较少的情况，可以用状态压缩的DP来做。比如用optmaskk表示已经访问过mask表示的结点集合，并且最后位于点k的最优解。,状态转移方程为：,optmaskk = min(optmask-ki + costik),i是所有与k相邻的点，mask-k指从mask除去k,62,