《数据结构与算法 图的遍历与连通性.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法 图的遍历与连通性.ppt（43页珍藏版）》请在三一办公上搜索。
1、1,图的遍历与连通性,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(Graph Traversal)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited。,2,辅助数组visited 的初始状态为 0,在图的遍历过程中,一旦某一个顶点 i 被访问,就立即让visitedi为 1,防止它被多次访问。图的遍历的分类:深度优先搜索 DFS(Depth First Search)广度优先搜索 BFS(Brea
2、dth First Search),3,深度优先搜索DFS(Depth First Search),深度优先搜索的示例,前进,回退,深度优先搜索过程 深度优先生成树,4,DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过
3、程,直到连通图中所有顶点都被访问过为止。,5,图的深度优先搜索算法,template void DFS(Graph/释放visited,6,templatevoid DFS(Graph/下一个邻接顶点,7,广度优先搜索BFS(Breadth First Search),广度优先搜索的示例,广度优先搜索过程 广度优先生成树,8,BFS在访问了起始顶点 v 之后,由 v 出发,依次访问 v 的各个未被访问过的邻接顶点 w1,w2,wt,然后再顺序访问 w1,w2,wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，如此做下去，直到图中所有顶点都被访
4、问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。,9,为了实现逐层访问,算法中使用了一个队列,以记忆正在访问的这一层和上一层的顶点,以便于向下一层访问。为避免重复访问,需要一个辅助数组 visited，给被访问过的顶点加标记。template void BFS(Graph/图中顶点个数,图的广度优先搜索算法,10,bool*visited=new booln;for(i=0;i Q;Q.EnQueue(loc);/顶点进队列,实现分层访问 while(!Q.IsEmpty()/循环,访问所有结点
5、 Q.DeQueue(loc);w=G.getFirstNeighbor(loc);/第一个邻接顶点 while(w=0)/若邻接顶点w存在 if(!visitedw)/若未访问过,11,cout G.getValue(w);/访问 visitedw=true;Q.EnQueue(w);/顶点 w 进队列 w=G.getNextNeighbor(loc,w);/找顶点 loc 的下一个邻接顶点/外层循环，判队列空否 delete visited;,12,连通分量(Connected component),当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历
6、到图中的所有顶点，只能访问到该顶点所在最大连通子图（连通分量）的所有顶点。若从无向图每一连通分量中的一个顶点出发进行遍历,可求得无向图的所有连通分量。例如，对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。,13,14,确定连通分量的算法,template void Components(Graph/输出连通分量,15,delete visited;例：以深度优先搜索方法从顶点 出发遍历图,建立深度优先生成森林。,A,有向图,深度优先生成森林,A,B,C,D,E,F,G,A,B,D,E,C,F,G,16,最小生成树(minimum cost spanning tree),使用不
7、同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1条边。构造最小生成树：假设有一个网络，用以表示 n 个城市之间架设通信线路，边上的权值代表架设通信线路的成本。如何架设才能使线路架设的成本达到最小？,17,构造最小生成树的准则必须使用且仅使用该网络中的 n-1 条边来联结网络中的 n 个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。,18,19,克鲁斯卡尔(Kruskal)算法,克鲁斯卡尔算法的基本思想：设有一个有 n 个顶点的连通网络 N=V,E,最初先构造一个只有 n 个顶点,没有
8、边的非连通图 T=V,图中每个顶点自成一个连通分量。当在 E 中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中;否则将此边舍去，重新选择一条权值最小的边。如此重复下去,直到所有顶点在同一个连通分量上为止。,20,Kruskal算法的伪代码描述,T=;/T是最小生成树的边集合/E是带权无向图的边集合while(T 包含的边少于n-1,21,算法的框架 利用最小堆(MinHeap)和并查集(DisjointSets)来实现克鲁斯卡尔算法。首先,利用最小堆来存放E中的所有的边,堆中每个结点的格式为在构造最小生成树过程中,利用并查集的运算检查依附一条边的两顶点
9、tail、head 是否在同一连通分量(即并查集的同一个子集合)上,是则舍去这条边；否则将此边加入T,同时将这两个顶点放在同一个连通分量上。,边的两个顶点位置 边的权值,22,随着各边逐步加入到最小生成树的边集合中,各连通分量也在逐步合并,直到形成一个连通分量为止。,构造最小生成树的过程,23,24,在求解最小生成树时，可以用邻接矩阵存储图，也可以用邻接表存储图。算法中使用图的抽象基类的操作，无需考虑图及其操作的具体实现。,25,出堆顺序(0,5,10)选中(2,3,12)选中(1,6,14)选中(1,2,16)选中(3,6,18)舍弃(3,4,22)选中(4,6,24)舍弃(4,5,25)选
10、中,并查集,原图,-2,-2,-2,-2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,2,-1,-1,-1,0,-2,2,0,0,0,0,0 1 2 3 4 5 6,-2,1,-1,1,-2,-1,-4,2,1,-2,-5,1,2,1,1,-7,1,1,2,1,1,F,(0,5,10),(2,3,12),(1,6,14),(1,2,16),(3,4,22),(4,5,25),26,普里姆(Prim)算法,普里姆算法的基本思想：从连通网络 N=V,E中的某一顶点 u0 出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合U中。以后每一步从
11、一个顶点在集合U中,而另一个顶点不在集合U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。,27,普里姆(Prim)的伪代码描述,选定构造最小生成树的出发顶点u0;Vmst=u0，Emst=;while(Vmst包含的顶点少于n,28,29,例子,H=(0,5,10),(0,1,28)ed=(0,5,10)Vmst=t,f,f,f,f,f,fVmst=t,f,f,f,f,t,f,30,H=(5,4,25),(0,1,28)ed=(5,4,25)Vmst=t,f,f,f,f,t,fVmst=t,f,f,f,t,t
12、,f,H=(4,3,22),(4,6,24),(0,1,28)ed=(4,3,22)Vmst=t,f,f,f,t,t,fVmst=t,f,f,t,t,t,f,31,H=(3,2,12),(3,6,18),(4,6,24),(0,1,28)ed=(3,2,12)Vmst=t,f,f,t,t,t,fVmst=t,f,t,t,t,t,f,H=(2,1,16),(3,6,18),(4,6,24),(0,1,28)ed=(2,1,16)Vmst=t,f,t,t,t,t,fVmst=t,t,t,t,t,t,f,32,H=(1,6,14),(3,6,18),(4,6,24),(0,1,28)ed=(1,6,
13、14)Vmst=t,t,t,t,t,t,fVmst=t,t,t,t,t,t,t,最小生成树中边集合里存入的各条边为：(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14),33,Prim算法适用于边稠密的网络。Kruskal算法不仅适合于边稠密的情形，也适合于边稀疏的情形。注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。,34,最短路径(Shortest Path),最短路径问题：在图中，从某一顶点（称为源点）到另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。问题解法 边上权
14、值非负情形的单源最短路径问题 Dijkstra算法(仅讲此算法)边上权值为任意值的单源最短路径问题 Bellman和Ford算法(不讲)所有顶点之间的最短路径 Floyd算法(不讲),35,边上权值非负情形的单源最短路径问题,问题的提法：给定一个带权有向图 D 与源点 v，求从 v 到 D 中其他顶点的最短路径。限定各边上的权值大于或等于 0。为求得这些最短路径,Dijkstra 提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点 v 到其它各顶点的最短路径全部求出为止。,艾兹格 W 迪杰斯特拉,Edsge
15、r Wybe Dijkstra，生于1930 年 5 月 11 日，卒于 2002 年 8 月 6 日，荷兰人。计算机科学家，毕业并就职于荷兰 Leiden 大学，早年钻研物理及数学，而后转为计算科学。曾在 1972 年获得过素有计算机科学界的诺贝尔奖之称的图灵奖。,37,Dijkstra逐步求解的过程,(v0,v1)(v0,v3)(v0,v4),1030100,60,90,(v0,v1,v2),(v0,v3,v4),(v0,v3,v2),50,60,(v0,v3,v2,v4),38,引入辅助数组dist。它的每一个分量disti表示当前找到的从源点 v0 到终点 vi 的最短路径的长度。初始
16、状态：若从v0到顶点vi有边,则disti为该边的权值；若从v0到顶点vi无边,则disti为。假设S是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0 出发，中间只经过 S 中的顶点便可到达的那些顶点vx(vx V-S)的路径中的一条。每次求得一条最短路径后,其终点vk 加入集合S，然后对所有的vi V-S，修改其 disti值。,39,Dijkstra算法可描述如下：,初始化：Sv0;distjEdge0j,j=1,2,n-1;/n为图中顶点个数 求出最短路径的长度：distkmin disti,iV-S;SSk;修改：distimindisti,distk+Edgeki
17、,对于每一个 iV-S;判断：若 S=V,则算法结束，否则转。,40,计算从单个顶点到其他各顶点最短路径的算法,void ShortestPath(Graph,41,Si=false;if(i!=v/将顶点 u 加入集合 S,42,for(k=0;k n;k+)/修改 w=G.GetWeight(u,k);if(!Sk/修改到 k 的最短路径,43,Dijkstra算法中各辅助数组的最终结果,从表中读取源点0到终点v的最短路径的方法:举顶点4为例 path4=2 path2=3 path3=0，反过来排列，得到路径 0,3,2,4，这就是源点0到终点4的最短路径。,0,4,1,2,3,10,50,10,20,60,30,100,序号,顶点,1,顶点,2,顶点,3,顶点,4,Dist,10,50,30,60,path,0,3,0,2,
