第三节 图的遍历

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

int visited[20]；

void DFS(MGraph G，int i，int n)

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

　int j；

　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(n²)

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

int visited[20] ；//全局量数组，用以标记某个顶点是否被访问过

void DFSl(ALGraph G， int i)

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

　EdgeNode *p；int j；

　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有路径相通的顶点都被访问过为止。

【例】

从V₀开始的广度优先搜索序列：V₀，V₁，V₃，V₄，V₂，V₆，V₈，V₅，V₇。

从V₈开始的广度优先搜索序列：V₈，V₄，V₀，V₁，V₆，V₃，V₂，V₇，V₅。

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

int visited[20]；

void BFS(MGraph G，int i，int n)

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

　cirQueue Q；　　　　　　　　　　　　　　　　 //定义一个队列

　int k，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)；　　　　　　　 //访问未曾访问过的顶点vj

　　　　　visited[j]=1；　　　　　　　　　　 //标记Vi已访问过

　　　　　EnQueue(&Q，j)；　　　　　　　 //顶点序号j入队

　　　　} //End_if

　　} //End_for

　} //End_while

}

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

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

Void BFSl(ALGraph G，int i，int n)

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

　CirQueue Q；　　　　　　　　　　 //定义一个队列指针

　int j，k；

　InitQueue(&Q)；　　　　　　　　　 //初始化队列

　EdgeNode *p；

　int visited[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)； //访问未曾访问过的顶点vj

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

　　　　　EnQueue(&Q，j);　 //顶点序号j入队

　　　　　}　　　　　　　　//End-if

　　　　p=p->next； 　　　　//使p指向Vk邻接表的下一个邻接点

　　　}　　　　　　　　　 //End_while

　　}　　　　　　　　　　 //End_while

}

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

注意：由于图G=（V，E）中顶点集合V与边的集合E中元素的排列是任意的，在采用邻接表存储以后，如果存放顶点结点的先后顺序不同，或者边结点的链接次序不同，在按照某种方式遍历图时，将会影响到顶点被访问的先后顺序，即经过遍历得到的遍历序列有可能不同。即使存储结构确定，如果指定的出发顶点不同，遍历结果也会不同。当然，对于某种已经确定的存储结构与指定的出发顶点，按照某种遍历方法得到的遍历结果应该是唯一的。

【真题选解】