《图的遍历和连通性.ppt》由会员分享，可在线阅读，更多相关《图的遍历和连通性.ppt（25页珍藏版）》请在三一办公上搜索。
1、7.1 基本术语7.2 存储结构7.3 图的遍历7.4 图的连通性7.5 图的应用,第7章 图,7.3 图的遍历,遍历：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。,遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,解决思路：可设置一个辅助数组 visited n，用来标记每个被访问过的顶点。它的初始状态为false，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited i为true，防止
2、它被重复访问。,怎样避免重复访问？,深度优先搜索和广度优先搜索,图常用的遍历：,一、深度优先搜索(DFS),Depth_First Search,基本思想：类似于树的先根遍历过程。,1、连通图的深度优先搜索遍历,步骤：访问起始点 v;依次从v的未被访问的邻接点出发深度优先遍历图直至图中所有和v有路径相通的顶点都被访问到。,v1,DFS 结果：,例1：,v2,v4,v8,v5,v3,v6,v7,起点,应退回到V8，因为V2已有标记,void DFS(Graph G,int v)/从顶点v出发，深度优先遍历G visitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex
3、(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFS/DFS,对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测。,2、非连通图的深度优先搜索遍历,步骤：访问起始点 v及图中所有和v有路径相通的顶点。如果图中尚有顶点未被访问，则以该顶点为起始点，进行深度优先搜索遍历。重复上述过程，直至所有顶点都已被
4、访问。,a,b,c,h,d,e,k,f,g,F F F F F F F F F,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例2:,0 1 2 3 4 5 6 7 8,8,1,2,3,4,5,6,7,0,void DFSTraverse(Graph G,Status(*Visit)(int v)/对图 G 作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visite
5、dv)DFS(G,v);/对尚未访问的顶点调用DFS,DFS 算法效率分析:,（设图中有 n 个顶点，e 条边）（1）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。（2）如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,结 论：稠密图适于在邻接矩阵上进行深度优先遍历；稀疏图适于在邻接表上进行深度优先遍历。,二、广度优先搜索(BFS),基本思想：仿树的层次遍历过程。,Breadth_First Search,在访问了起始点v之后，依次访
6、问 v的各个未曾访问过的邻接点；然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,步骤：,v1,BFS 结果：,例1：,v3,BFS 结果：,v4 v5,起点,起点,v2 v1 v6,v9 v8 v7,例2：,讨论：,答:利用一个队列结构记录顶点访问顺序，将访问的每个顶点入队，然后，再依次出队，出队时访问其邻接点并将邻接点入队。,（2）如何避免重复访问某个顶点？,（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，应采用何
7、种方式记录顶点访问顺序？,答：创建一个一维数组visited0.n-1（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。,（3）广度优先搜索有回退的情况吗？,答：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此广度优先搜索不是一个递归的过程，其算法也不是递归的。,void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnum;+v)if
8、(!visitedv)/v 尚未访问/BFSTraverse,visitedv=TRUE;Visit(v);/访问vEnQueue(Q,v);/v入队列while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点w入队列/if/while,BFS 算法效率分析:,如果使用邻接表来表示图，则BFS循环的总时间代价为 d0+d1+dn-1=O(e)，其中的 di 是顶
9、点 i 的度。如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n 个元素），总的时间代价为O(n2)。,（设图中有 n 个顶点，e 条边）,空间复杂度相同，都是O(n)(借用堆栈或队列装n个顶点）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,DFS与BFS之比较：,生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均适用）,思考1：若对连通图进行遍历，得到的是什么？一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，为深度优先生成
10、树。由广度优先搜索得到的生成树，为广度优先生成树。,思考2：若对非连通图进行遍历，得到的是什么？各连通分量的生成树，即图的生成森林！,7.4 图的连通性,1.求无向图的生成树（或生成森林）,例1：画出下图的生成树。,DFS生成树,邻接表,v0,v2,v1,v4,v3,BFS生成树,v0,例2：画出下图的生成森林（或极小连通子图）,下面选用邻接表方式来求深度优先生成森林,DFS结果：ABMJLCF DE GHKI,子图1：,子图2：,子图3：,A,F,C,M,L,B,J,A,F,C,M,L,B,J,生成森林,注：图的生成树（生成森林）不唯一！,2.求无向网的最小生成树,目标：在网络的多个生成树中
11、，寻找一个各边权值之和最小的生成树。即在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n1条线路使总费用最少？,典型用途：,最小生成树（MST）的 性质如下：,V是顶点集，U是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0,v0)必在最小生成树上。,求MST有多种算法，但最常用的是以下两种：,Prim（普里姆）算法 Kruskal（克鲁斯卡尔）算法,Prim算法特点:顶点归并，与
12、边数无关，适于稠密网。Kruskal算法特点：边归并，适于求稀疏网。,对边操作,对顶点操作,普里姆算法的基本思想:,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。如图所示：,a,b,c,d,e,g,f,例如:,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,所得生成树权值和,=14+8+3+5+16+21=67,集合U,集合V-U,u0,v0,方法：设置一个辅助数组，对当前VU集中的每个顶点，记录和顶
13、点集U中顶点相连接的代价最小的边。对每个属于V-U的顶点vi，在辅助数组中存在一个相应的分量closedgei-1，它包含两个域，其中lowcost存储该边上的权。显然，closedgei-1.lowcostMincost(u,vi)|uU,存储方式：struct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,7,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,19 14 1819 5 7 12 5 3 7 3 8 21 14 12 8 16 21 2718 16 27,（a b c d e f g),Prim算法的时间效率O（n2）,（a b c d e f g),具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法的基本思想：,Kruskal算法的时间效率O（elog2e）,
