图论相关算法课件.ppt

《图论相关算法课件.ppt》由会员分享，可在线阅读，更多相关《图论相关算法课件.ppt（62页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、图图 论论（Elementary Graph Algorithms）图的定义图的定义l图是由顶点集合以及顶点间的关系的集合图是由顶点集合以及顶点间的关系的集合组成的一种关系的数学表示组成的一种关系的数学表示l G =（V，E）l其中顶点是由有穷非空集合其中顶点是由有穷非空集合l顶点之间的关系（边）是有穷集合顶点之间的关系（边）是有穷集合lPath(x,y)表示从表示从x到到y的一条单向通路，的一条单向通路，它是有方向的它是有方向的图的分类图的分类l有向图有向图：图中的边是有方向的。图中的边是有方向的。E(x,y)和和E(y,x)表示的边不同表示的边不同l无向图无向图：图中的边是没有方向的。：图

2、中的边是没有方向的。l完全图完全图：n个顶点的图两两连边，即有个顶点的图两两连边，即有 n(n-1)/2条边，则此图为条边，则此图为n的完全图。的完全图。用用K n表示表示图的一些概念图的一些概念l邻接顶点：邻接顶点：如果如果(u,v)E(G),则称则称u与与v互互为邻接顶点为邻接顶点l子图子图：设有两个图：设有两个图G(V,E)和和G(V,E)，若，若V V 且且E E，则称图，则称图G是图是图G的子图的子图l权权：某些图的边上标有相关的数字，称为：某些图的边上标有相关的数字，称为该边的权值该边的权值l顶点的度顶点的度 一个顶点一个顶点V的度是与它相连边的条数，的度是与它相连边的条数，记为记

3、为Deg(V).l顶点的入度顶点的入度 一个顶点一个顶点V的入度是以它为终点有向的入度是以它为终点有向边的条数，记为边的条数，记为InDeg(V)l顶点的出度顶点的出度 一个顶点一个顶点V的入度是以它为起点有向的入度是以它为起点有向边的条数，记为边的条数，记为OutDeg(V)l路径路径 在图在图 G(V,E)中中,若从顶点若从顶点 vi 出发出发,沿沿一些边经过一些顶点一些边经过一些顶点 Vp1,Vp2,Vpm，到达，到达顶点顶点Vj。则称顶点序列。则称顶点序列(Vi Vp1 Vp2.Vpm Vj)为从顶点为从顶点Vi 到顶点到顶点 Vj 的路径。它经过的边的路径。它经过的边(Vi,Vp1)

4、、(Vp1,Vp2)、.、(Vpm,Vj)应是属于应是属于E的的边。边。图的存储表示图的存储表示邻接矩阵邻接矩阵(Adjacency Matrix)l设图设图G=(V,E)是一个有是一个有N个顶点的图，图的个顶点的图，图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组G.edgeNNl定义：定义：G.edgeij=1 If(i,j)E(G)0 otherwise0213G.edgeij=0 1 01 0 120 0 0 012G.edgeij=0 1 1 11 0 0 01 0 0 11 0 1 0无向图的临界矩阵是对称的无向图的临界矩阵是对称的有向图的邻接矩阵往往是不对称的有向图的邻接矩阵往往

5、是不对称的 图的存储表示图的存储表示邻接表邻接表(Adjacency List)0213010023320123 Data adj dest link dest link dest link 同一个顶点发出的边链接在同一个边链表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边，结点中另一个顶每一个链结点代表一条边，结点中另一个顶点的下表点的下表dest和指针和指针link图论相关算法图论相关算法广度优先搜索广度优先搜索l通常用队列通常用队列(先进先出先进先出,FIFO)实现实现Q=起点起点s;标记标记s为己访问为己访问;while(Q非空非空)取取Q队首元素队首元素u;u出队

6、出队;所有与所有与u相邻且未被访问的点进入队列相邻且未被访问的点进入队列;标记标记u为已访问为已访问;广度优先搜索广度优先搜索l由由BFS得到的路径是原图中从得到的路径是原图中从S到到T的边数的边数最少的路径最少的路径l广度优先搜索树不唯一广度优先搜索树不唯一广度优先搜索的例子广度优先搜索的例子012543678012543678012543678 0 1 2 1 1 2 2 4 3 t=0;void BFS(int s)/从从 s 开始遍历开始遍历 int queuemaxn,tail,head;head=tail=0;queuehead=s;depths=0;times=t+;visits

7、=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;深度优先搜索深度优先搜索l相关概念相关概念递归实现递归实现结点颜色：结点颜色：l白色（开始），灰色（发现），黑色（结束）白色（开始），灰色（发现），黑色（结束）一个结点总是从白色变为灰色，再变为黑色一个结点总是从白色变为灰色，再变为黑色当所有点都变为黑色时，遍历结束当所有点都变为黑色时，遍历结

8、束时间戳时间戳(timestamp):du表示一个结点开始被访表示一个结点开始被访问的时间，问的时间，fu表示一个结点结束访问的时间表示一个结点结束访问的时间深度优先搜索深度优先搜索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;深度优先搜索深度优先搜索l每个顶点的每个顶点的du fulDFS中，中，v是是u的子孙的子孙 dud

9、vfv=2）的标号的）的标号的GCD为为1深度优先搜索深度优先搜索l割点与割边割点与割边如果从图中删去某点和与该点相关联的边后，图如果从图中删去某点和与该点相关联的边后，图不再连通，那么这个点叫做割点不再连通，那么这个点叫做割点(cut point)。如果从图中删去某条边后，图不再连通，那么这如果从图中删去某条边后，图不再连通，那么这条边叫做割边或桥条边叫做割边或桥(bridge)。关节点：图中的关节点指这样一个顶点，如关节点：图中的关节点指这样一个顶点，如果删除它，图就会被分割成至少两个分离的果删除它，图就会被分割成至少两个分离的子图。关节点也称作分离顶点或子图。关节点也称作分离顶点或割点割

10、点。0123456789101112顶点0、4、5、6、7和11为关节点。割点、割边以及连通分量时间戳：时间戳：dfni表示结点表示结点i是第是第dfni个被访问到的结点。有的时候我们个被访问到的结点。有的时候我们 还要记录某个结点被遍历并检查完毕的时间。还要记录某个结点被遍历并检查完毕的时间。void dfs(v)dfnv=+times;/记录访问结点的时间戳记录访问结点的时间戳 visitv=1;for 寻找一个寻找一个v的相邻节点的相邻节点uif(visitu=0)thenDFS(u);LMABCFIDGJEHKABLFMJCHKGIDE连通图GG的深度优先生成树树边：深度优先搜索树中的

11、实线表示树边，在DFS过程中，从v点访问u点时，若u没有被访问过，则边(v,u)为树边。回边：深度优先搜索树中的虚线表示回边，在DFS过程中，从v点访问u点时，若u点已经访问过，则边(v,u)为回边。ABLFMJCHKGIDE由深度优先生成树可得出两类关节点的特性：(1)若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。因为图中不存在联结不同子树中顶点的边，因此，若删去根顶点，生成树便变成生成森林。如上图中的顶点A。(2)若生成树中某个非叶子顶点v，它的子树中的任一结点均没有指向v的祖先的回边，则v为关节点。因为，若删去v，则其子树和图的其他部分就被分割开来。如上图中的顶点B、D和G。

12、我们在DFS的基础上增加一个low数组，lowi用来记录i及i的子孙相连的辈分最高的祖先的访问时间戳。lowv=min(dfnv,loww,dfnk);w是顶点v在深度优先树上的孩子结点；k是顶点v在深度优先树上由回边联结的祖先结点；当lowj=dfnv,表明w及其子孙均无指向v的祖先的回边，则该顶点v必为关节点。具体算法如下：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!

13、=w)/w已经访问过了，说明从v到w有一条回边，w是v的祖先 lowv=min(lowv,dfnw);桥：图中的桥（桥：图中的桥（bridgebridge）是一条边，如果删除这条边，将）是一条边，如果删除这条边，将把连通图分离成两个断开的子图。无桥的图称作边连通图把连通图分离成两个断开的子图。无桥的图称作边连通图（edge-connected graphedge-connected graph）。）。0123456789101112这个图不是边连通图。边0-5、6-7和11-12（带阴影）为桥。在任何DFS树中，当且仅当不存在回边连通w的子孙与w的祖先时，树边v-w是一座桥。与割点类似的，我们

14、定义low和dfn。父子边e=uv，当且仅当lowv dfnu的时候，e是割边。有向图的强连通分量在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。下图中，子图1,2,3,4为一个强连通分量，因为顶点1,2,3,4两两可达。5,6也分别是两个强连通分量。求有向图的强连通分量一般采用Kosaraju算法或Tarjan算法，两者的时间复杂度都是O(n+m)。下面着重介绍一下Tarj

15、an算法。Tarjan算法Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。dfs时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。我们仍然定义dfni为节点i搜索的次序编号(时间戳)，lowi为i或i的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出:当dfn(u)=low(u)时，以u为根的搜索子树上的所有节点构成一个强连通分量。void tarjan(int i)int j;dfni=lowi=+times;/为节点u设定次序编号和Low初值 instacki=true;Stack+Stop=i;/将节点

16、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);从

17、节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，dfn6=low6=4，找到了一个强连通分量。退栈到u=v为止，6为一个强连通分量。返回节点5，发现dfn5=low5=3，退栈后5为一个强连通分量。返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4存在向节点1的回边，节点1还在栈中，所以low4=dfn1=1。节点6已经出栈，不再访问6，返回3，(3,4)为树边，所以low3=low4=1。继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以low2=4。返回1后，发现DFN1=LOW1，把栈中节点全部取出，组成一个连通分量1,3,4,2。至此，算法结束。经过该

18、算法，求出了图中全部的三个强连通分量1,3,4,2,5,6。Kosaraju算法 Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。kosaraju算法的步骤如下：(1)在有向图G上，从某个顶点出发进行DFS，并按其所有邻接点的搜索都完成(即退出DFS函数)的顺序将顶点排列起来。Kosaraju算法 Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。kosaraju算法的步骤如下：(2)在有向图G上，从最后完成搜索的顶点出发，在图G的逆图G上进行DFS，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那

19、个顶点出发，继续做逆图中的DFS，直至有向图中的所有顶点都被访问到为止。每一次调用DFS作逆图中的遍历所访问到的顶点集便是有向图G中的一个强连通分量。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 dfs

20、n(int pos)/逆向DFS int i,j;visitpos=true;idpos=ans;/求出连通分量 for(i=0;iadjnpos.size();i+)j=adjnposi;if(!visitj)dfsn(j);拓扑排序l图的结点存在一个拓扑序：如果图中有边图的结点存在一个拓扑序：如果图中有边(u，v)，则，则u必定排在必定排在v的前面的前面l拓扑排序在有向无环图拓扑排序在有向无环图(DAG)上进行上进行l拓扑序列不一定唯一拓扑序列不一定唯一拓扑排序拓扑排序l利用利用DFS，当节点，当节点u已经扩展完成，将标记已经扩展完成，将标记颜色置为黑时，将颜色置为黑时，将u加入已排序列的

21、顶部，加入已排序列的顶部，搜索完成时，节点序列为拓扑序搜索完成时，节点序列为拓扑序l经过拓扑排序的顶点以与其完成时刻相反经过拓扑排序的顶点以与其完成时刻相反的顺序出现的顺序出现拓扑排序拓扑排序l算法算法(1)计算每个点的入度，入度为计算每个点的入度，入度为0的点加入队列的点加入队列Q(2)从从Q中取出一个点中取出一个点p，输出，输出(3)所有与所有与p相邻的点的入度减相邻的点的入度减1。如果新得到了。如果新得到了入度为入度为0的点，则加入队列的点，则加入队列Q。(4)转步骤转步骤(2),直到所有点都输出完毕直到所有点都输出完毕如果在执行过程中发现找不到入度为如果在执行过程中发现找不到入度为0的

22、点的点,说说明图中存在环明图中存在环拓扑排序拓扑排序l1 3 2 4 5 6 7 8(不唯一不唯一)l如何生成最小字典序的拓扑序列？如何生成最小字典序的拓扑序列？可以使用最小堆维护当前入度为可以使用最小堆维护当前入度为0的节点的节点21348756最小生成树最小生成树l生成树：由生成树：由G的的n-1条边构成的无环的子图，条边构成的无环的子图，这些边的集合成为生成树。这些边的集合成为生成树。l最小生成树：所有生成树中权值最小的一最小生成树：所有生成树中权值最小的一个边集个边集T为最小生成树，确定树为最小生成树，确定树T的问题成的问题成为最小生成树问题。为最小生成树问题。lprim算法算法lkr

23、uskal算法算法primprim算法算法l任取一个顶点加入生成树；任取一个顶点加入生成树；l在那些一个端点在生成树里，另一个端点在那些一个端点在生成树里，另一个端点不在生成树里的边中，取权最小的边，将不在生成树里的边中，取权最小的边，将它和另一个端点加进生成树。它和另一个端点加进生成树。l重复上一步骤，直到所有的顶点都进入了重复上一步骤，直到所有的顶点都进入了生成树为止。生成树为止。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+)i

24、nt min=INT_MAX;for(j=1;j=n;j+)if(!usedj&closestjmin)min=closestj;now=j;sum+=min;usednow=1for(j=1;j=n;j+)if(mapnowj&mapnowjclosestj)closestj=mapnowj;return sum;时间复杂度为时间复杂度为O(n2)。(用堆维护最小优先级队列可以达到用堆维护最小优先级队列可以达到O(vlogv+elogv),有兴趣的同学可以有兴趣的同学可以自己实现自己实现)Kruskal算法算法l对所有边从小到大排序；对所有边从小到大排序；l依次试探将边和它的端点加入生成树，

25、如依次试探将边和它的端点加入生成树，如果加入此边后不产生圈，则将边和它的端果加入此边后不产生圈，则将边和它的端点加入生成树；否则，将它删去；点加入生成树；否则，将它删去；l直到生成树中有了直到生成树中有了n-1条边，即告终止。条边，即告终止。l算法的时间复杂度算法的时间复杂度O(eloge)kruskal算法实现的数据结构算法实现的数据结构l一维数组，将所有边按从小到大的顺序存在数组里面一维数组，将所有边按从小到大的顺序存在数组里面l并查集并查集l先把每一个对象看作是一个单元素集合，然后按一定顺序先把每一个对象看作是一个单元素集合，然后按一定顺序将相关联的元素所在的集合合并。能够完成这种功能的

26、集将相关联的元素所在的集合合并。能够完成这种功能的集合就是并查集。合就是并查集。对于并查集来说，每个集合用一棵树表示。对于并查集来说，每个集合用一棵树表示。它支持以下操作：它支持以下操作：Union(Root1,Root2)/Union(Root1,Root2)/合并两个集合；合并两个集合；getRootgetRoot(x)/(x)/搜索操作（搜索编号为搜索操作（搜索编号为x x所在树的根）。所在树的根）。树的每一个结点有一个指向其父结点的指针。树的每一个结点有一个指向其父结点的指针。并查集的处理过程并查集的实现并查集的实现int rootMAXN;/定义根数组，记录每个节点的父亲节点定义根数

27、组，记录每个节点的父亲节点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;kruskal的实现的实现linit();/初始化

28、lsort(.)/按权值对边进行排序lfor 每条边(u,v)Elint r_1=getRoot(u),r_2=getRoot(v);lif(r_1!=r_2)lunion(u,v);欧拉路l欧拉路：经过图中每条边恰好一次的路欧拉路：经过图中每条边恰好一次的路l欧拉回路：起点和终点相同的欧拉路欧拉回路：起点和终点相同的欧拉路欧拉路l无向图存在欧拉路的条件无向图存在欧拉路的条件如果图连通，且所有的点都是偶数度，则有欧拉如果图连通，且所有的点都是偶数度，则有欧拉回路。回路。如果图连通，且恰有两点是奇数度，则有欧拉路。如果图连通，且恰有两点是奇数度，则有欧拉路。且欧拉路的起止点为这两个奇数度点。且欧

29、拉路的起止点为这两个奇数度点。对重边、自环的情况仍适用。对重边、自环的情况仍适用。欧拉路l有向图存在欧拉路的条件有向图存在欧拉路的条件如果图连通，且每个点的入度等于出度，则存在如果图连通，且每个点的入度等于出度，则存在欧拉回路。欧拉回路。如果图连通，且恰有一点如果图连通，且恰有一点u的出度比入度大的出度比入度大1，另，另有一点有一点v的出度比入度小的出度比入度小1，其余的出度等于出度，其余的出度等于出度，则存在欧拉路，起点为则存在欧拉路，起点为u，终点为，终点为v。对重边、自环的情况仍适用。对重边、自环的情况仍适用。欧拉路l套圈算法套圈算法void Euler(int start)for(in

30、t i=1;i=E;i+)if(!visiti&from=start)visiti=1;Euler(to);path+top=i;l倒序倒序path为欧拉路为欧拉路欧拉路l例题：例题：给定一组单词，问这些单词能否连成一串，使得给定一组单词，问这些单词能否连成一串，使得前面一个单词的最后一个字母和后面一个单词的前面一个单词的最后一个字母和后面一个单词的第一个字母相同。第一个字母相同。欧拉路lSample Input6 alohaarachniddog gopher rat tiger 3 oak maple elm lSample Outputaloha.arachnid.dog.gopher.

31、rat.tiger*欧拉路l解法：解法：先判断连通性先判断连通性每个单词相当于在首字母和尾字母之间连一条边每个单词相当于在首字母和尾字母之间连一条边得到一个最多得到一个最多26个点的有向图个点的有向图求欧拉路求欧拉路汉密尔顿路l汉密尔顿路：经过图中每个点恰好一次的汉密尔顿路：经过图中每个点恰好一次的路路l汉密尔顿回路：起点和终点相同的汉密尔汉密尔顿回路：起点和终点相同的汉密尔顿路顿路l常见方法：状态压缩常见方法：状态压缩DP 汉密尔顿路l对于点数较少的情况，可以用状态压缩的对于点数较少的情况，可以用状态压缩的DP来做。比如用来做。比如用optmaskk表示已经访表示已经访问过问过mask表示的结点集合，并且最后位于表示的结点集合，并且最后位于点点k的最优解。的最优解。l状态转移方程为：状态转移方程为：optmaskk=min(optmask-ki+costik)i是所有与是所有与k相邻的点，相邻的点，mask-k指从指从mask除去除去k