《图的搜索算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《图的搜索算法幻灯片.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的搜索算法第1页，共39页，编辑于2022年，星期五图的邻接表表示对图（有向或无向）G=（为方便记，假定V=1,2,n），其邻接表表示是一个由|V|个链表组成数组，对每个u V，链表Adju称为对应顶点u的邻接表。它包含G中所有与u相邻的顶点。每个邻接表中顶点通常是按任意顺序存放的。第2页，共39页，编辑于2022年，星期五6.1广度优先搜索1问题的理解与描述给定一个图（有向或无向）G=和其中的一个源顶点s，广度优先搜索系统地探索G的边以“发现”从s出发每一个可达的顶点：发现从s出发距离为k+1的顶点之前先发现距离为k的顶点。搜索所经路径中的顶点，按先后顺序构成“父子关系”：先发现的顶点u，
2、并由u出发发现与其相邻的顶点v，则称u为v的父亲。由于每个顶点只有最多一个顶点作为它的父亲，所以搜索路径必构成一棵根树（树根为起始顶点s）G。我们把这棵树称为G的广度优先树广度优先树。与此同时，我们还计算出了从s到这些可达顶点的距离（最少的边数即“最短路径”）。这样，图的广度搜索问题形式化表述如下。输入输入：图G=，源顶点sV。输出输出：G的广度优先树G以及树中从树根s（源顶点）到各节点的距离。第3页，共39页，编辑于2022年，星期五对一个无向图的BFS操作第4页，共39页，编辑于2022年，星期五2算法的伪代码描述BFS(G,s)1for每个顶点uVG-s2docoloruWHITE3du
3、4uNIL5colorsGRAY6ds07Q8ENQUEUE(Q,s)9whileQ10douDEQUEUE(Q)11foreachvAdju12do ifcolorv=WHITE13thencolorvGRAY14vu15dvdu+116ENQUEUE(Q,v)17 coloruBLACK18returnandd第5页，共39页，编辑于2022年，星期五3算法的正确性引理引理6-1从源顶点s到任何顶点v的距离必不超过运行BFS后过此顶点的d属性。引理引理6-2设队列Q=v1,v2,vr。则dvrdv1+1（即对尾元素的d属性不超过队首元素的d属性加1），且dv1dv2.dvr。定理定理6-3
4、运行BFS后，图G中各顶点v的d属性记录了s到v的距离。第6页，共39页，编辑于2022年，星期五4算法的运行时间第14行的循环重复|V|次。另一方面，由于每条边在搜索过程中有且仅有一次被访问，第917行两重循环嵌套内的操作被执行|E|次。所以BFS的总运行时间是(V+E)。于是，广度优先搜索运行于G的邻接表示规模的线性时间内。第7页，共39页，编辑于2022年，星期五6.2深度优先搜索深度优先搜索深度优先搜索（DepthFirstSearch，DFS）所遵循的策略，如同其名称所云，是在图中尽可能“更深”地进行搜索。在深度优先搜索中，对最新发现的顶点v若此顶点尚有未探索过从其出发的边就探索之。
5、当v的所有边都被探索过，搜索“回溯”到从其出发发现顶点v的顶点。此过程继续直至发现所有从源点可达的顶点。若图中还有未发现的顶点，则以其中之一为新的源点重复搜索，直至所有的顶点都被发现。与BFS中源顶点是指定的稍有不同。DFS搜索轨迹G将形成一片森林深度优先森林深度优先森林第8页，共39页，编辑于2022年，星期五1问题的理解与描述在深度优先搜索过程中对每一个顶点u跟踪两个时间：发现时间du和完成时间f u。du记录首次发现（u由白色变成灰色）时刻，f u记录完成v的邻接表检测（变成黑色）时刻。输入输入：图G=。输出输出：G的深度优先森林G以及图中各顶点在搜索过程中的发现时间和完成时间。第9页，
6、共39页，编辑于2022年，星期五2算法的伪代码描述DFS(G)1foreachvertexuVG2docoloruWHITE3uNIL4time05S6foreachvertexsVG7do ifcolors=WHITE8then colorsGRAY9dstimetime+110PUSH(S,s)11whileS12do uTOP(S)13if v Adjuandcolorv=WHITE14then colorvGRAY15vu16dvtimetime+117PUSH(S,v)18else coloruBLACK19f utime time+120POP(S)21returnd,f,and
7、第10页，共39页，编辑于2022年，星期五DFS施于一个有向图的过程第11页，共39页，编辑于2022年，星期五3算法的运行时间DFS的运行时间如何？第12行的循环(V)。内嵌于第1420行操作对G的每条边执行一次，因此耗时所以DFS的运行时间为(V+E)。第12页，共39页，编辑于2022年，星期五6.2.3有向无圈图的拓扑排序DFS算法可以修改成能对各条边在遇到它们时进行分类。关键的思想是，每一条边(u,v)在首次被探索时可以根据顶点v的颜色来分类（但是进边和跨边不能区分）：白色（WHITE）意味着一条树枝边；灰色（GRAY）意味着一条回边；黑色（BLACK）意味着一条进边或跨边。图G是
8、无圈的充分必要条件是G的一次深度优先搜索不产生回边。第13页，共39页，编辑于2022年，星期五问题的理解与描述一个有向无圈图G=（DAG）的拓扑排序是其所有顶点的一个线性排列，使得若边(u,v)包含在G中，则u在排列中必出现在v前（若图不是无圈的，则不可能有此线性排列）。一个图的拓扑排序可被视为将图的所有顶点水平排列时，所有的有向边从左指向右。输入输入：有向图G。输出输出：若G是DAG，输出G的各顶点的一个拓扑排序，否则输出出错信息。第14页，共39页，编辑于2022年，星期五算法的伪代码描述TOPLOGICAL-SORT(G)1foreachvertexuVG2docoloruWHITE3
9、acyclicitytrue4top-logicS5foreachvertexsVG6do ifcolors=WHITE7thencolorsGRAY8PUSH(S,s)9whileS10do uTOP(S)11if v Adjuandcolorv=GRAY12thenacyclicityfalse13if v Adjuandcolorv=WHITE14then colorvGRAY15PUSH(S,v)16elsecoloruBLACK17PUSH(top-logic,u)18POP(S)19 if acyclicity=true20thenreturntop-logic21elseprin
10、tGisnotaDAG!“由于TOPLOGICAL-SORT的运行时间与DFS的运行时间一致，所以，可以在时间(V+E)内计算有向无圈图G=的拓扑排序。第15页，共39页，编辑于2022年，星期五6.3有向图的强连通分支有向图G=(V,E)的一个强连通分支CV是一个使得其中每一对顶点u和v均有uv及vu，即顶点u和v是相互可达且对任意wV-C，Cw中至少有一对顶点不能相互可达的顶点集合。把一个有向图G中的各个强连通分支收缩为一个“顶点”，则将得到一个称为G的分支图的有向图。第16页，共39页，编辑于2022年，星期五定理定理6-4有向图的分支图是一个有向无圈图。对G的分支图中的各个顶点（G的各
11、个强连通分支Ci，i=1,2,k）定义发现时间和完成时间d(Ci)=minu Ci du及f(Ci)=maxu Ci fu。第17页，共39页，编辑于2022年，星期五1问题的理解与描述计算强连通分支的问题形式化表示为：输入输入：有向图G。输出输出：G的各强连通分支C1,C2,Ck。引理引理6-5设C和C是有向图G=(V,E)的两个不同的强连通分支。在一次深度优先搜索中其完成时间分别为f(C)和f(C)。若有边(u,v)ET，其中u C 及v C。则f(C)lowv25then lowvlowv26ifrootdegree127then 将s插入A根节点是关节点28for u1ton29do
12、ifus30then iflowudu31then将u插入A非根节点u是关节点32returnA由于过程ARTICULATION是基于DFS的计算无向连通图的关节点，所以其时间复杂度和DFS的一样，为(V+E)。第26页，共39页，编辑于2022年，星期五6.5流网络与最大流问题我们可以把一个有向图解释为一个“流网络”并利用它来回答关于物流的问题。想象一个流动于某系统的物流从生产出该物品的某源点出发，汇集于某消费该物品的接收地。源点以不变的速率生产物品，汇点以相同的速率消费该物品。系统中任一点的物“流”直观地看就是在该点物品的移动速率。流网络可以用来模型化流过管道的流体，通过流水线的零部件，通
13、过电网的电流，通过通信网络的信息，等等。第27页，共39页，编辑于2022年，星期五1问题的理解与描述（1）流网络。一个流网络流网络G=是一个有向图，其中的每一条边(u,v)E有一个非负的容量容量c(u,v)0。若(u,v)E我们假定c(u,v)=0。即我们在网络中标识两个顶点：一个称为源点源点，记为s；一个称为汇点汇点，记为t。假定每一个顶点都位于从源点到汇点之间的某条路径上。即，对每一个顶点v V，有一条路径svt。所以，该图是连通的，且|E|V|-1。第28页，共39页，编辑于2022年，星期五（2）流设G=是一个网络，其容量函数为c。设s为该网络的源点，t是汇点。G中的一个流流是一个实
14、数值函数f：V V R它满足如下3条性质：容量约束：容量约束：对所有的u,v V,要求f(u,v)c(u,v)。斜对称性：斜对称性：对所有的u,v V,要求f(u,v)=-f(v,u)。流守恒性：流守恒性：对所有的u V-s,t,要求。量f(u,v)，可以是正的、零或负的，称为是从顶点顶点u到顶点到顶点v的流的流。一个流f 的值定义为：第29页，共39页，编辑于2022年，星期五（3）最大流问题在最大流问题中，已知一个网络G及其源点s和汇点t，希望找到具有最大值的流。形式化为：输入输入：网络G=，其中源点为s，汇点为t，定义在VV上的容量c。输出输出：定义在VV上的流f：VVR，使得最大。第3
15、0页，共39页，编辑于2022年，星期五（4）剩余网络直观地看，对给定的网络及一个流，其剩余网络由可以接受更多流的边组成。更形式化地说，假定有一个网络G=，其源点为s，汇点为t。设f 为G中的一个流，考虑一对顶点u,v V。不超过容量c(u,v)，从u到v可以添加的流量是(u,v)的剩余容量，定义如下：cf(u,v)=c(u,v)-f(u,v)给定一个流网络G=和一个流f，G的根据f的剩余网络记为Gf=，其中Ef=(u,v)V V:cf(u,v)0第31页，共39页，编辑于2022年，星期五（5）增广路径给定网络G=(V,E)及一个流f，一条增广路径增广路径p是剩余网络Gf中的一条从s到t的简
16、单路径。根据剩余网络的定义，增广路径上的每一条边(u,v)将接纳一些从u到v的附加正流而不会违背该边上的容量限制。定理定理6-6若f 是G的一个最大流，则G关于f 的剩余网络Gf 中不存在增广路径。第32页，共39页，编辑于2022年，星期五（6）流网络的割流网络G=(V,E)的一个割割(S,T)是V的一个分为S和T=V S，且s S及t T 的一个划分。若f是一个流，则跨越割(S,T)的净流净流定义为。割(S,T)的容量容量为。一个网络的最小割最小割是该网络的容量最小的割。引理引理6-7流网络G中的任一个流f，以G的任一割的容量为上界。第33页，共39页，编辑于2022年，星期五2算法的伪代
17、码描述定理定理6-7设流网络G关于流f 不存在增广路径，则f 是G的一个最大流。EDMONDS-KARP(G,s,t,c)1ff02cfc3GfG4(,d)BFS(Gf,s)5while dt6do p由决定的从s到t的路径7cpmin cf(u,v):(u,v)在p中8for p中的每条(u,v)9do fu,vfu,v+cp10fv,u-fu,v11cfu,vcfu,v-cp12cfv,ucfv,u+cp13Gf由cf决定的有向图14(,d)BFS(Gf,s)15returnf第34页，共39页，编辑于2022年，星期五基本Ford-Fulkerson算法的执行。(a)(d)是while循
18、环的连续迭代。每一部分的左边展示的是第4行确定的剩余网络Gf，带阴影的是其增广路径p。每一部分的右边展示了在f上加上fp的结果。(a)中的剩余网络就是输入网络G。(e)是while循环最后检测的剩余网络。其中已无增广路径了，所以展示在(d)中的流f 就是最大流。第35页，共39页，编辑于2022年，星期五3算法的运行时间引理引理6-8算法EDMONDS-KARP运行于源点为s，汇点为t的流网络G=(V,E)，对任意vV-s,t，其在剩余网络中的最短路径df v随着流的增广而单调增加。定理定理6-9若EDMONDS-KARP算法运行于源为s汇为t的一个流网络G=(V,E)上，则算法的运行时间为O
19、(V E2)。第36页，共39页，编辑于2022年，星期五4二部图的最大匹配问题给定一个无向图G=(V,E)，一个匹配是边的一个子集M E使得对所有的v V，至多有M中的一条边与v关联。说一个顶点v是匹配的，若M中有一条与v关联的边；否则，v是不匹配的。一个最大匹配是含有最多边的一个匹配，即对于任一匹配M，我们有|M|M|。假定顶点集合可以划分成V=LR，其中L和R是不相交的且E中的所有边都连接L和R中的顶点。我们还假定V中的每一个顶点至少有一条边与之关联。称G为二部图。第37页，共39页，编辑于2022年，星期五一个二部图G=(V,E)，点划分为V=LR。(a)一个势为2的匹配。(b)一个最大匹配，其势为3。第38页，共39页，编辑于2022年，星期五5寻求二部图的最大匹配可以利用EDMONDS-KARP算法在|V|和|E|的多项式时间内，在一个无向二部图G=(V,E)中寻求一个最大匹配。(a)一个二部图，其顶点划分为V=L R。用带阴影的边表示出一个最大匹配。(b)对应的流网络及其一个最大流。每一条边具有一个单位的容量。带有阴影的边具有流1，而其他的边不带有流。从L到R的带有阴影的边对应于二部图中的最大匹配。第39页，共39页，编辑于2022年，星期五