14学时图的遍历.

数据结构与算法第14学时图的遍历2图（graph）图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。它定义为G=(V，E)ABCDEABCDE0123401234无向图有向图无向图G=(V,E)顶点集V={A,B,C,D,E}边集E={(A,B),(A,C),(B,D),(C,D),(C,E),(D,E)}有向图G=(V,E)顶点集V={A,B,C,D,E}边集E={A,C,B,A,B,D,C,D,D,E,E,C}内容回顾：图的存储结构-邻接矩阵邻接矩阵顺序存储ABCDE0110010110110010100100110内容回顾：主要内容：–图遍历概念–图的两种遍历(重点、难点）1.深度优先遍历2.广度优先遍历1.图遍历的概念从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。•深度优先遍历(depth-firstsearch,DFS)•广度优先遍历(breadth-firstsearch,BFS)V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5深度遍历：V1,V2,V4,V5,V8,V3,V6,V7V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5深度遍历：V1,V3,V6,V7,V2,V5,V8,V4图的深度优先遍历（DFS）深度优先遍历(depth-firstsearch,DFS)•1)任选图中某个未被访问的顶点v作为起点,访问v并标记为已访问;•2)递归访问与v相邻且未被访问过的顶点.7V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V6V3V7深度遍历：V1V2V4V8V5V6V3V7课堂练习：8V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V3V6V7V5深度遍历：V1V3V7V6V2V4V8V5课堂练习:9图的广度优先搜索（BFS）方法：类型于树的层次遍历（1）访问初始点v，接着访问v的所有未被访问过的邻接点v1，v2，…，vt。（2）按照v1，v2，…，vt的次序，访问每一个顶点的所有未被访问过的邻接点。（3）依次类推，直到图中所有和初始点v有路径相通的顶点都被访问过为止。从图中某顶点v出发：1.访问顶点v2.访问v的所有未被访问的邻接点w1,w2,…wk3.依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到图中所有访问过的顶点的邻接点都被访问到。V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5广度优先遍历1:V1,V2,V3,V4,V8,V5,V6,V7广度优先遍历2:V1,V3,V2,V6,V7,V4,V5,V8图的广度遍历（BFS）11V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8课堂练习：12V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V5V6V7V8图的遍历（复习）深度遍历：V1V2V4V8V5V6V3V7当无向图是连通图、有向图是强连通图时，只需选一个起点，就能一次性遍历完图中所有顶点。V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V6V7V8图的广度优先搜索（BFS）注意：无向非连通图或有向非强连通图可能需要选择几个起点进行图的遍历。非连通图的遍历？V5第14页图的深度遍历（DFS）算法分析Vw1SG1SG2SG3w2w3w2W1、W2和W3均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。访问顶点V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。第15页从图解可见：1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志visited[w]”。2.如何判别V的邻接点是否被访问？Vw1SG1SG2SG3w2w3w2图的深度遍历（DFS）算法分析例如：abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg访问标志:访问次序:012345678图的深度遍历（DFS）算法分析160273854图的深度优先遍历算法例G1bdac12341234acdbdatafirstarc3241^^^^adjvexnextarc深度遍历次序：a-c-d-b深度优先遍历需辅助数组，visited[0..n-1]，记录每个结点访问标志◆递归算法：//邻接表存储voidDFS(ALGraph*G，intv){ArcNode*p;intw;visited[v]=1;//置已访问标记printf(“%d”，v);//printf(“%c”,G-adjlist[V].data);p=G-adjlist[v].firstarc;while(p!=NULL){w=p-adjvex;if(visited[w]==0)DFS(G，w);//若w顶点未访问，递归访问它p=p-nextarc;//p指向顶点v的下一条边的边头节点}}Intvisited[n]={0};PPP18图的深度优先遍历算法VoidDFSM(MGraph*G,inti)//邻接矩阵是0,1{intj;printf(“%C”,G-vexs[i]);visited[i]=1;For(j=0;jG-n;j++)//依次遍历vi的邻接点If(G-edges[i][j]=1&&visited[j])DFSM(G,j);V1V3V2V4V1V2V3V4V10111V21001V31000V41100深度遍历次序：V1-v2-v4-v319图的广度优先搜索算法分析类似于按层次遍历二叉树的方式来遍历图,体现先进先出的特点，用队列实现。在遍历的过程中需要辅助数组，visited[0..n]，记录每个结点访问标志。为了顺次访问路径长度为1，2，3，...的顶点，需要附设队列以存储已被访问的路径长度为1，2，3...的顶点。图的广度优先搜索算法例G1bdac01230123acdbvexdatafirstarc2130^^^^广度遍历次序：0-2-1-3adjvexnextarcvoidBFS(ALGraph*G，intv){ArcNode*p;intw，i;intqueue[MAXV]，front=0，rear=0;intvisited[MAXV];for(i=0;iG-n;i++)visited[i]=0;printf(%2d，v);visited[v]=1;rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){front=(front+1)%MAXV;w=queue[front];p=G-adjlist[w].firstarc;while(p!=NULL){if(visited[p-adjvex]==0){Printf(“%2d”，p-adjvex);visited[p-adjvex]=1;rear=(rear+1)%MAXV;queue[rear]=p-adjvex;}p=p-nextarc;}}printf(\n);}PP21广度遍历：V1V2V3V4图的广度优先搜索算法voidBFSM(MGgraph*g;intk)//邻接矩阵//从v0出发广度优先遍历图G{inti,j;iniqueque(Q);//初始化设置空队列Qenqueque(&Q,k);//v0进队列Qprintf(“%c”,G-vexs[k];visited[k]=TRUE;while(!QueueEmpty(&Q))//当队列不空时{i=dequeque(&Q);//队头元素v出队列for(j=1;j=G-n;j++){if(G-edges[i][j]==1&&visited[j]){printf(“%c”,G-vexs[j]);visited[j]=TRUE;enqueque(&Q,j);//访问过的vj进队}}};V1V3V2V4V1V2V3V4V10111V21001V31000V41100228.3.4非连通图的遍历但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点，分别进行遍历，才能够访问到图中的所有顶点；对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点；否则不能访问到所有顶点，为此同样需要再选初始点，继续进行遍历，直到图中的所有顶点都被访问过为止。23采用深度优先搜索遍历非连通无向图的算法如下：DFS1(ALGraph*G){inti;for(i=0;iG-n;i++//遍历所有未访问过的顶点if(visited[i]==0)DFS(G，i);}24采用广度优先搜索遍历非连通无向图的算法如下：BFS1(ALGraph*G){inti;for(i=0;iG-n;i++)//遍历所有未访问过的顶点if(visited[i]==0)BFS(G，i);}25实例：图遍历的应用例8.3假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。解：采用遍历方式判断无向图G是否连通。这里用深度优先遍历方法，先给visited[]数组（为全局变量）置初值0，然后从0顶点开始遍历该图。在一次遍历之后，若所有顶点i的visited[i]均为1，则该图是连通的；否则不连通。对应的算法如下：