第九章图2

合肥工业大学计算机与信息学院19.3图的遍历图的遍历——访问图中所有顶点一次且仅且一次。深度优先搜索遍历图的两种遍历算法广度优先搜索遍历9.3.1深度优先搜索遍历（DepthFirstSearch)这一问题求解包括几个部分。1.基本算法从顶点v0出发深度优先搜索遍历图G的dfs(v0)描述如下：(1)访问v0；(2)依次从v0的未被访问过的邻接点出发深度遍历。合肥工业大学计算机与信息学院2dfs(8)dfs(9)dfs(4)dfs(3)9.3.1深度优先搜索遍历下面以下图为例来讨论dfs算法的执行过程：调用dfs(1)此箭头表示是从遍历运算dfs(1)中调用dfs(2)，即从顶点1直接转到2此虚箭头表示是在dfs(3)执行完毕后返回到遍历运算dfs(2)中，即从顶点3返回到267125348109dfs(1)dfs(2)dfs(5)dfs(6)dfs(7)dfs(10)在访问顶点3后，由于顶点3的邻接点已全被访问，故dfs（3）执行到此结束，应返回到调用层，即返回到dfs(2)dfs(1)包含如下两部分操作：（1）访问顶点1；（2）依次执行dfs(2)和dfs(8)合肥工业大学计算机与信息学院39.3.1深度优先搜索遍历将dfs（1）执行过程中所搜索的边连接起来（有标注的边），得到一棵生成树----dfs生成树。6712534810967125348109原图及其搜索示意图dfs(1)生成树合肥工业大学计算机与信息学院9.3.1深度优先搜索遍历4V1V7V4V3V5V6V2V8verdata8∧V87V76V65V54V43V32V21V101∧32∧7∧6∧54firstadj24∧5∧725∧6G.vertexDFS访问序列：V1V2V3V6V5V8V7V4出发点合肥工业大学计算机与信息学院59.3.1深度优先搜索遍历下面讨论dfs算法的设计。为此，先回顾一下dfs(v0)的描述：(1)访问v0；(2)依次从v0的未被访问过的邻接点出发深度遍历。分析：由算法描述可知：①访问顶点v0的基本操作：可用visite(v0)简单表示。②设置访问标志数组visted[]，并约定：某顶点vi未被访问时，visted[i]==FALSE（初值）vi被访问过后，visted[i]==TRUE（初值）③求邻接点可以采用两个函数：firstadj(G,v)：返回v的第一个邻接点（号），或-1（不存在时）。nextadj(G,v,w);返回v的邻接点中处于邻接点w之后的邻接点号,或-1（不存在时）访问v0时，visted[i]=TRUE;合肥工业大学计算机与信息学院6YN9.3.1深度优先搜索遍历由讨论可得到dfs算法的流程图如下：由此得深度遍历基本算法如下:voidgraph::dfs(intv){intw;visite(v);visited[v]=true;w=firstadj(v);while(w!=-1){if(!visited[w])dfs(w);w=nextadj(v,w);}}Yvisite(v);visted[v]=TRUE;W==-1?W被访问过？Ndfs(w);w=nextadj(v,w);w=firstadj(v)：合肥工业大学计算机与信息学院79.3.1深度优先搜索遍历问题：（1）dfs算法是否适用于有向图？（2）如何设置标志数组visited[]的初值？能否在dfs算法中设置？（3）从某顶点出发是否能保证访问到所有顶点？或者说：选择一个起点调用一次dfs算法，能否实现对整个图的遍历？2.遍历整个图的算法dfs算法在应用于非连通图，或者是某些有向图时，某一次调用就不能保证访问到所有顶点。如下图所示。61253467125348109合肥工业大学计算机与信息学院89.3.1深度优先搜索遍历为此，需要重新选择起点来调用dfs算法。如何选择新的起点？起点应满足什么条件？构成对整个图的遍历算法如下：voidgraph::Trave_DFS(){inti;for(i=0;iCurrentVertex;i++)visited[i]=false;//赋初值for(i=0;iCurrentVertex;i++)//选择起点if(!visited[i])dfs(i);}算法复杂度：采用邻接矩阵存储Ｏ(n2)采用邻接表存储O(n+e)合肥工业大学计算机与信息学院99.3.1深度优先搜索遍历3.深度遍历算法的应用问题：（1）如何设计算法以判断给定的无向图是否是连通的？（2）如何设计算法以求解给定的无向图中的边数？（3）设计算法以判断给定的无向图是树。（4）设计算法以判断给定的有向图是以v0为根的有向树。合肥工业大学计算机与信息学院109.3.1深度优先搜索遍历例1设计算法以求解无向图G的连通分量的个数。分析：选择起点的次数就是图G的连通分量数，可通过计数调用dfs算法的次数实现。intgraph::numofGC(){inti;intk=0;//k用于连通分量的计数for(i=0;iCurrentVertex;i++)visited[i]=false;for(i=0;iCurrentVertex;i++)if(visited[i]==false){k++;dfs(i);}//用k来累计连通分量个数returnk;}遍历整个图的算法Trave_DFS中的原来的部分合肥工业大学计算机与信息学院119.3.1深度优先搜索遍历例2设计算法求出无向图G的边数。分析：可通过执行dfs函数搜索每个顶点的邻接点来实现。算法如下：intE=0;//全局变量voidgraph::dfs(intv){intw;visited[v]=true;//设置访问标志（访问结点的其它操作被省去）w=firstadj(v);while(w!=-1){E++;//此处意味着找到一条边，故累计到变量E中if(visited[w]==false)dfs(w);w=nextadj(v,w);}}dfs算法中原有的操作coutE/2;合肥工业大学计算机与信息学院9.3.1深度优先搜索遍历例3设计算法以判断给定的无向图是树。分析：无向图G是树的条件是，G必须是无回路的连通图，或n-1条边的连通图。intgraph::vnum()//得到当前顶点个数{returnCurrentVertex;}k=G.numofGC();//图的连通分量个数boolIS_tree(graphG，intk){if(k==1&&E/2==(G.vnum()-1))//连通图且边数等于顶点数-1returntrue;elsereturnfalse;}12合肥工业大学计算机与信息学院9.3.1深度优先搜索遍历例4：设计算法以判断给定的有向图是以v0为根的有向树分析：有向树顶点的入度仅为0（v0）和1（其余各顶点），因此，如果从v0出发深度遍历，每个顶点仅访问一次就符合定义要求。voidgraph::dfs(intv){intw;visited[v]=true;num++;//对访问顶点计数（省去Trave_DFS操作）w=firstadj(v);while(w!=-1){if(visited[w]==false)dfs(v);elsejudge=false;//执行到此，表明顶点w被重复访问，设置失败标志w=nextadj(v,w);}}13合肥工业大学计算机与信息学院9.3.1深度优先搜索遍历判断是否为以v0为根的有向树：boolIS_diTree(graphG,intv0){inti;judge=true;//judge用于记录判断的信息，初始为truefor(i=0;iG.vnum();i++)visited[i]=false;num=0;G.dfs(v0);if(num==G.vnum()&&judge)returntrue;//如果一次遍历访问所有顶点且顶点没被重复访问elsereturnfalse;}14合肥工业大学计算机与信息学院159.3.2广度优先搜索遍历9.3.2广度优先搜索遍历（Breadth_firstsearch)广度优先遍历——由近及远逐层访问顶点（典型的层次遍历）1.基本算法从顶点v0出发广度优先搜索遍历图的算法bfs(v0):（1）访问v0（2）依次访问v0的各邻接点。（3）设最近一层访问序列为vi1，vi2，……，vik，则依次访问vi1，vi2，……，vik的未被访问过的邻接点。（4）重复上述操作（3），直到所有可达的邻接点被访问完为止。合肥工业大学计算机与信息学院169.3.2广度优先搜索遍历bfs(1)的执行过程如下图所示。其中用红线标注搜索路线。将搜索的便连起来得到bfs生成树。6712534810967125348109bfs生成树合肥工业大学计算机与信息学院9.3.2广度优先搜索遍历17V1V7V4V3V5V6V2V8访问序列：V1V2V4V5V6V7V8出发点V3verdata8∧V87V76V65V54V43V32V21V101∧32∧7∧6∧54firstadj24∧5∧725∧6合肥工业大学计算机与信息学院189.3.2广度优先搜索遍历算法构思：(1)设访问标志数组；(2)为了能依次访问上一层次的访问序列中的各顶点的邻接点，需要设置一个队列以保存上一层次的顶点，(3)既然涉及到队列（不妨Q），则需要安排队列的运算：(a)初始化；(b)入队：每访问一个顶点v，除了访问操作、设置标志外，还要将其入队。(c)出队：从队列中删除一个顶点v，这意味着要依次访问v的所有未被访问过的邻接点。合肥工业大学计算机与信息学院199.3.2广度优先搜索遍历广度遍历的基本算法如下：voidgraph::bfs(intv){intw;queueQ;intx;visite(v);visited[v]=true;Q.append(v);while(!Q.empty()){Q.get_front(x);v=x;Q.serve();w=firstadj(v);while(w!=-1){if(!visited[w]){visit(w);visited[w]=true;Q.append(w);}w=nextadj(v,w);}}}合肥工业大学计算机与信息学院209.3.2广度优先搜索遍历2.遍历整个图的算法voidgraph::Trave_BFS(){inti;for(i=0;iCurrentVertex;i++)visited[i]=false;for(i=0;iCurrentVertex;i++)if(!visited[i])bfs(i);}合肥工业大学计算机与信息学院9.3.2广度优先搜索遍历3.广度遍历算法的应用例：设计算法求顶点v0到图中其余每个顶点的最短路径（以弧数为单位）,要求尽可能节省时间。解：用bfs生成树——以v0为根的bfs生成树能给出v0到每个顶点的最短路径。2197018342650123456789-1001122344合肥工业大学计算机与信息学院9.3.2广度优先搜索遍历voidgraph::bfsSpanTree(intv){intw;queueQ;inti,x;for(i=0;iCurrentVertex;i++)visited[i]=false;visited[v]=true;Q.append(v);parentof[v]=-1;//记录顶点v的双亲结点为-1while(!Q.empty()){Q.get_front(x);v=x;Q.serve();w=firstadj(v);while(w!=-1){if(!visited[w]){visited[w]=true;Q.append(w);parentof[w]=v;}//记录顶点w的双亲结点vw=nextadj(v,w);}}for(i=0;iCurrentVertex;i++)printpath(parentof,i);//输出v到顶点i的最短路径}22合肥工业大学计算机与信息学院9.3.2广度优先搜索遍历voidprintpath(intparentof[