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

第三节图的遍历

图的遍历：从某个顶点出发，沿着某条搜索路径对图中每个顶点做

且仅做一次访问。图的遍历最常用的是深度优先搜索遍历和广度优先

搜索遍历两种方法。

一、深度优先搜索遍历

1、深度优先搜索遍历思想：

深度优先搜索(DepthFirstSearch,DFS)遍历类似于树的前序(先

根)遍历。假设初始状态是图中所有顶点都未曾访问过，则可从图G中

任选一顶点V为初始出发点，首先访问出发点V,并将其标记为已访

问过；然后依次从V出发搜索V的每个邻接点W,若W未曾访问

过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中

所有和V有路径相通的顶点都被访问到；若此时图中仍有顶点未被访

问，则另选一个未曾访问的顶点作为起点，重复上述过程，直到图中

所有顶点都被访问到为止。

从Vo开始的深度优先搜索序列：V。，V1,V2,V5,V4,V6,V3,

V7,V8o

从V8开始的深度优先搜索序列：V8,V4,Vo,V1,V2,V5,V3,

V6,V7o

2、以邻接矩阵为存储结构的深度优先搜索遍历算法

intvisited[20];

voidDFS(MGraphG,inti,intn)

{〃从顶点Vi出发，深度优先搜索遍历图G(邻接矩阵结构)

intj;

printf("V%d^",i);〃假定访问顶点vi以输

出该顶点的序号代之

visited[i]=l;〃标记vi已访问过

for(j=0;j<n;j++)〃依次搜索vi的每个邻

接点

if(G.arcs[i][j]==l&&!visited[j])

DFS(G,j,n);〃若(Vi,Vj)e(G),且Vj

未被访问过，则从开始递归调用

)

该算法的时间复杂度为O(n2)

3、以邻接表为存储结构的深度优先搜索遍历算法

intvisited[20];〃全局量数组，用以标记某个顶点是否被访问过

voidDFSI(ALGraphG,inti)

{〃从顶点Vi出发，深度优先搜索遍历图G(邻接表结构)

EdgeNode*p;intj;

printf("V%d^",i);〃假定访问顶点vi以

输出该顶点的序号代之

visited[i]=l;〃标记vi已访问过

p=G[i].link;〃取Vi邻接表的表头

指针

while(p!=NuLL)〃依次搜索vi的每个

邻接点

{j=p->adjvex;//]为vi的一个邻接

点序号

if(!visited[)])

DFSI(GJ);〃若(vi,vj)GE(G),且

vj未被访问过，则从开始递归调用

p=p->next;〃使P指向vi的下

一个邻接点

}//End-while

)

该算法的时间复杂度为O(n+e)o

二、广度优先搜索遍历

1、广度优先搜索遍历思想

广度优先搜索(BFS)遍历类似于树的按层次遍历。其基本思想是：首

先访问出发点Vi,接着依次访问Vi的所有未被访问过的邻接点Vil,

Vi2，…，Vit,并均标记为已访问过,然后再按照Vil,Vi2，…，Vit

的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问

过，依次类推，直到图中所有和初始出发点Vi有路径相通的顶点都被

访问过为止。

【例】

从Vo开始的广度优先搜索序列：Vo,V1,V3,V4,V2,V6,V8,

V5,V7o

从V8开始的广度优先搜索序列：V8,V4,Vo,Vl,V6,V3,V2,

v7,v5o

2、以邻接矩阵为存储结构的广度优先搜索遍历算法

intvisited[20];

voidBFS(MG、phG,inti,intn)

{〃从顶点Vi出发，广度优先搜索遍历图G(邻接矩阵结构)

cirQueueQ;〃定义一个

队歹I」

intk,j;

InitQueue(&Q);〃初始化队

printf("v%d->",i)〃假定访问顶

点vi用输出该顶点的序号代之

visited[i]=l;〃标记Vi已访

问过

EnQueue(&Q,i);〃将已访问的顶

点序号i入队

while(!QueueEmpty(&Q))〃当队列非空

时，循环处理vi的每个邻接点

{k=DeQueue(&Q);〃删除队头元

素

for(j=0;j<n;j++)〃依次搜索Vk

的每一个可能的

{if(G.arcs[k][j]==l&&!visited[j])

{printf("V%l,j);〃访问未曾访问

过的顶点vj

visited[j]=l;〃标记Vi已访问

过

EnQueue(&Q,j);〃顶点序号j入队

}//Endjf

}//End_for

}//End_while

)

该算法的时间复杂度为0(n2)

3、以邻接表为存储结构的广度优先搜索遍历算法

VoidBFSI(ALGraphG,inti,intn)

{〃从顶点Vi出发，广度优先搜索遍历图G

CirQueueQ;〃定义一个队列指针

intj,k;

InitQueue(&Q);〃初始化队列

EdgeNode*p;

intvisited[20];

printf("v%d-*",i);〃假定访问顶点vi以输出

该顶点的序号代之

visited[i]=l;〃标记vi已访问过

EnQueue(&Q,i);〃将已访问的顶点序号i入

队

while(!QueueEmpty(&Q))〃循环处理vi的每个邻

接点

{k=DeQueue(&Q);〃删除队头元素

p=G[k].link;〃取vk邻接表的表头指针

while(p!=NULL)〃依次搜索vk的每一个可能的

邻接点

{j=p->adjvex;//Vj为Vk的一个邻接点

if(!visited。])〃若vj未被访问过

{printf("V%d^",j);〃访问未曾访问过的顶点vj

visited[j]=1;〃标记vj已访问过

EnQueue(&Q,j);/©点序号j入队

}//End-if

p=p->next;〃使p指向Vk邻接表的下一个

邻接点

}//End_while

}//End_while

)

该算法的时间复杂度为

O(n+e)o

注意：由于图G=(V,E)中顶点集合V与边的集合E中元素的排

列是任意的，在采用邻接表存储以后，如果存放顶点结点的先后顺序

不同，或者边结点的链接次序不同，在按照某种方式遍历图时，将会

影响到顶点被访问的先后JII页序,即经过遍历得到的遍历序列有可能不

同。即使存储结构确定，如果指定的出发顶点不同，遍历结果也会不

同。当然，对于某种已经确定的存储结构与指定的出发顶点，按照某

种遍历方法得到的遍历结果应该是唯一的。

【真题选解】

(例题•单选题)在下图中，从顶点1

出发进行深度优先遍历可得到的序列是

0

A.1234567

B.1426375

C.1425367

D.1246537

隐藏答案

【答案】B

【解析】从顶点1出发进行深度优先遍历：先访问1,然后可以访

问2,接下来不可能访问3,（所以选项A错误），可以访问4,接下

来可以5,不可能访问6,（所以选项D错误）。先访问1,然后可

以访问4,再访问2,接下来可以6,不可能访问5,（所以选项C错

误）。选项B:1426375是从顶点1出发进行深度优先遍历可得

到的序列。

012345

（例题•单选题）已知含6个顶点（VO,VI,。国。011000

1工1101100

）的无向图的邻接矩阵如图所11QQ01

V2,V3,V4,V5"13010000

4*4000QQ1

示，则从顶点V0出发进行深度优先遍历可能得5国5001QI0

到的顶点访问序列为（）

A.（VO,VI,V2,V5,V4,V3）

B.（