大学《数据结构》第六章：图-第三节-图的遍历

第三节图的遍历图的遍历：从某个顶点出发，沿着某条搜索路径对图中每个顶点做且仅做一次访问。图的遍历最常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。一、深度优先搜索遍历1、深度优先搜索遍历思想：深度优先搜索(DepthFirstSearch，DFS)遍历类似于树的前序(先根)遍历。假设初始状态是图中所有顶点都未曾访问过，则可从图G中任选一顶点V为初始出发点，首先访问出发点V，并将其标记为已访问过；然后依次从V出发搜索V的每个邻接点W，若W未曾访问过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中所有和V有路径相通的顶点都被访问到；若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。【例】从V0开始的深度优先搜索序列：V0，V1，V2，V5，V4，V6，V3，V7，V8。从V8开始的深度优先搜索序列：V8，V4，V0，V1，V2，V5，V3，V6，V7。2、以邻接矩阵为存储结构的深度优先搜索遍历算法intvisited[20]；voidDFS(MGraphG，inti，intn){//从顶点Vi出发，深度优先搜索遍历图G(邻接矩阵结构)intj；printf("V%d→"，i)；//假定访问顶点vi以输出该顶点的序号代之visited[i]=1；//标记vi已访问过for(j=0；j<n；j++)//依次搜索vi的每个邻接点if(G.arcs[i][j]==1&&!visited[j])DFS(G，j，n)；//若(Vi，Vj)∈(G)，且Vj未被访问过，则从开始递归调用｝该算法的时间复杂度为O(n2)3、以邻接表为存储结构的深度优先搜索遍历算法intvisited[20]；//全局量数组，用以标记某个顶点是否被访问过voidDFSl(ALGraphG，inti){//从顶点Vi出发，深度优先搜索遍历图G(邻接表结构)EdgeNode*p；intj；printf("V%d→"，i)；//假定访问顶点vi以输出该顶点的序号代之visited[i]=1；//标记vi已访问过p=G[i].1ink；//取Vi邻接表的表头指针while(p!=NuLL)//依次搜索vi的每个邻接点{j=p->adjvex；//j为vi的一个邻接点序号if(!visited[j])DFSl(G，j)；//若(vi，vj)∈E(G)，且vj未被访问过，则从开始递归调用p=p->next；//使p指向vi的下一个邻接点｝//End-while｝该算法的时间复杂度为O(n+e)。二、广度优先搜索遍历1、广度优先搜索遍历思想广度优先搜索(BFS)遍历类似于树的按层次遍历。其基本思想是：首先访问出发点Vi，接着依次访问Vi的所有未被访问过的邻接点Vi1，Vi2，…，Vit，并均标记为已访问过，然后再按照Vi1，Vi2，…，Vit的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依次类推，直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。【例】从V0开始的广度优先搜索序列：V0，V1，V3，V4，V2，V6，V8，V5，V7。从V8开始的广度优先搜索序列：V8，V4，V0，V1，V6，V3，V2，V7，V5。2、以邻接矩阵为存储结构的广度优先搜索遍历算法intvisited[20]；voidBFS(MGraphG，inti，intn){//从顶点Vi出发，广度优先搜索遍历图G(邻接矩阵结构)cirQueueQ；//定义一个队列intk，j；InitQueue(&Q)；//初始化队列printf("v%d→"，i)//假定访问顶点vi用输出该顶点的序号代之visited[i]=1；//标记Vi已访问过EnQueue(&Q，i)；//将已访问的顶点序号i入队while(!QueueEmpty(&Q))//当队列非空时，循环处理vi的每个邻接点{k=DeQueue(&Q)；//删除队头元素for(j=0；j<n；j++)//依次搜索Vk的每一个可能的{if(G.arcs[k][j]==1&&!visited[j]){printf("V%d→"，j)；//访问未曾访问过的顶点vjvisited[j]=1；//标记Vi已访问过EnQueue(&Q，j)；//顶点序号j入队}//End_if}//End_for}//End_while}该算法的时间复杂度为O(n2)3、以邻接表为存储结构的广度优先搜索遍历算法VoidBFSl(ALGraphG，inti，intn){//从顶点Vi出发，广度优先搜索遍历图GCirQueueQ；//定义一个队列指针intj，k；InitQueue(&Q)；//初始化队列EdgeNode*p；intvisited[20]；printf("v%d→"，i);//假定访问顶点vi以输出该顶点的序号代之visited[i]=1;//标记vi已访问过EnQueue(&Q，i);//将已访问的顶点序号i入队while(!QueueEmpty(&Q))//循环处理vi的每个邻接点{k=DeQueue(&Q)；//删除队头元素p=G[k].1ink;//取vk邻接表的表头指针while(p!=NULL)//依次搜索vk的每一个可能的邻接点{j=p->adjvex；//Vj为Vk的一个邻接点if(!visited[j])//若vj未被访问过{printf("V%d→"，j)；//访问未曾访问过的顶点vjvisited[j]=1;//标记vj已访问过EnQueue(&Q，j);//顶点序号j入队}//End-ifp=p->next；//使p指向Vk邻接表的下一个邻接点}//End_while}//End_while}该算法的时间复杂度为O(n+e)。注意：由于图G=（V，E）中顶点集合V与边的集合E中元素的排列是任意的，在采用邻接表存储以后，如果存放顶点结点的先后顺序不同，或者边结点的链接次序不同，在按照某种方式遍历图时，将会影响到顶点被访问的先后顺序，即经过遍历得到的遍历序列有可能不同。即使存储结构确定，如果指定的出发顶点不同，遍历结果也会不同。当然，对于某种已经确定的存储结构与指定的出发顶点，按照某种遍历方法得到的遍历结果应该是唯一的。【真题选解】（例题•单选题）在下图中，从顶点1出发进行深度优先遍历可得到的序列是()A．1234567B．1426375C．1425367D．1246537隐藏答案【答案】B【解析】从顶点1出发进行深度优先遍历：先访问1，然后可以访问2，接下来不可能访问3，（所以选项A错误），可以访问4，接下来可以5，不可能访问6，（所以选项D错误）。先访问1，然后可以访问4，再访问2，接下来可以6，不可能访问5，（所以选项C错误）。选项B：1426375是从顶点1出发进行深度优先遍历可得到的序列。（例题•单选题）已知含6个顶点(V0，V1，V2，V3，V4，V5)的无向图的邻接矩阵如图所示，则从顶点V0出发进行深度优先遍历可能得到的顶点访问序列为()A．(V0，V1，V2，V5，V4，V3)B．(V0，V1，V2，V3，V4，V5)C．(V0，V1，V5，V2，V3，V4)D．(V0，V1，V4，V5，V2，V3)隐藏答案【答案】A【解析】根据