第二十一讲图的遍历

第七章图滨州学院计算机科学技术系图的遍历

从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。

遇到的问题：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

为避免重复访问，可设一个标志顶点是否被访问过的辅助数组visited[],它的初始状态为0，在图遍历过程中，一旦某一个顶点i被访问，就修改

visited[i]为1，防止它被多次访问。

从图中某个顶点V0出发，访问此顶点，然后选择一个与V0邻接且未被访问的顶点W为初始顶点，再从W出发进行深度优先搜索,

直至图中所有顶点都被访问到。一、深度优先搜索遍历连通图的深度优先搜索遍历深度优先搜索DFS(DepthFirstSearch)深度优先搜索的示例深度优先搜索过程深度优先生成树DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。1.深度优先搜索遍历连通图的过程类似于树的先根遍历；为每个顶点设立一个“访问标志visited[w]”。2.如何判别V的邻接点是否被访问？voidDFSTraverse(GraphG,Status(*Visit)(intv)

){//对图

G作深度优先遍历

VisitFunc=Visit；for(v=0;v<G.vexnum;++v)visited[v]=false;//访问标志数组初始化

for(v=0;v<G.vexnum;++v)

//对尚未访问的顶点调用DFS

if(!visited[v])

DFS(G,v);}Bolean

visited[MAX];Status(*VisitFunc)(intv);voidDFS(GraphG,intv){

//从第v个顶点出发，深度优先搜索遍历图

Gvisited[v]=true;VisitFunc(v);for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);

//对v的尚未访问的邻接顶点w递归调用DFS}//DFS

首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历abchdeifgFFFFFFFFFTTTTTTTTTachdifebgachifedbg访问标志:访问次序:例如:012345678voidDFSTraverse(GraphG){//对图G作深度优先遍历。for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化for(v=0;v<G.vexnum;++v)

//对尚未访问的顶点调用DFS

if(!visited[v])DFS(G,v);}算法分析设图中有n个顶点，e条边。如果用邻接表表示图，沿

firstout

链可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的邻接点所需的时间为O(n2)。二、广度优先搜索遍历Vw1w8w3w7w6w2w5w4对连通图，从起始点V到其余各顶点必定存在路径。

其中，V->w1,V->w2,V->w8

的路径长度为1；V->w7,V->w3,V->w5

的路径长度为2；V->w6,V->w4

的路径长度为3。w1Vw2w7w6w3w8w5w4

从图中的某个顶点V出发，并在访问V0之后依次访问V0的各个未被访问的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。

若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。广度优先搜索BFS(BreadthFirstSearch

)广度优先搜索的示例

广度优先搜索过程 广度优先生成树

使用广度优先搜索在访问了起始顶点v之后，由v出发，依次访问v的各个未曾被访问过的邻接顶点w1,w2,…,wt，然后再顺序访问w1,w2,…,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接点，…如此做下去，直到图中所有顶点都被访问到为止。

广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。

为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。

与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组visited[]，给被访问过的顶点加标记。

voidBFSTraverse(GraphG，status(*Visit)(intv){//广度优先搜索遍历图G

for(v=0;v<G.vexnum;++v)

visited[v]=false;//初始化访问标志

InitQueue(Q);

//初始化队列Q

for(v=0;v<G.vexnum;++v)

if(!visited[v])

{//v尚未访问

}}//BFSTraverse……EnQueue(Q,v);

//v入队列while(!QueueEmpty(Q)){

DeQueue(Q,u);

//队头元素出队为u并准备访问

Visited[u]=true;Visit(u);//访问u

for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))if(!visited[w]){

EnQueue(Q,w);

//下一个要访问的顶点w入队列

}//if}//while算法分析如果使用邻接表表示图，则循环的总时间代价为d0+d1+…+dn-1=O(e)，其中的di是顶点i的度。如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的n个元素，总的时间代价为O(n2