数据结构中图的遍历算法

【前言】数据结构中图的遍历算法由文秘帮小编整理而成，但愿对你的学习工作带来帮助。根据搜索路径方向的不同，遍历图的方法可分深度优先搜索遍历和广度优先搜索遍历，又根据编制算法的方法不同，可分为递归遍历算法和非递归遍历算法，再考虑到图的邻接矩阵和邻接表两种不同存储结构，综合起来图的搜索遍历共可分为八种。 下面以图1为例，分别介绍图的各...

摘要：本文根据图的存储结构、搜索路径及编制算法的方法不同，详尽地给出八种不同的图的遍历算法思想。即：从图的邻接矩阵和邻接表两种不同存储结构，再考虑到递归和非递归两种遍历思想的不同，分别把深度优先搜索遍历和广度优先搜索遍历分为四种不同的遍历方法。其目的是：通过本文的讨论，使初学者及高职学生能充分掌握数据结构中图的不同遍历算法并能正确的给出图的各种遍历程序。

关键词：图；存储结构；算法

中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)17-21516-03

遍历算法在数据结构中是最普通的运算方法也是所有其它算法的基础。由于图的遍历比线性表、树的结构的遍历算法要复杂，因此着重对图的遍历算法进行讨论，具有更普遍的意义。图的遍历就是从图中指定的某顶点作为遍历的起始出发点，按照一定搜索遍历路径，对图中所有顶点仅作一次访问的过程。

因为图的复杂性，在图中的任何顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能沿着某条路径又回到了该顶点。为了避免重复访问图中的同一个顶点，在搜索访问过程中必须记住每个顶点是否被访问过，为此可设置一个向量visited[vexnum],它的初始值为{0}，一旦访问了第i顶点，便将visited[i]置为1。

根据搜索路径方向的不同，遍历图的方法可分深度优先搜索遍历和广度优先搜索遍历，又根据编制算法的方法不同，可分为递归遍历算法和非递归遍历算法，再考虑到图的邻接矩阵和邻接表两种不同存储结构，综合起来图的搜索遍历共可分为八种。

下面以图1为例，分别介绍图的各种优先遍历方法。

1 深度优先搜索遍历

假定给定图G的初态是所有顶点均未访问过，在G中任选一顶点i作为遍历的起始点，则深度优先搜索遍历基本思想是：

首先访问起始顶点i,并将其访问标记置为已访问过，即visited[i]=1；然后依次从顶点i的未被访问的邻接点中选顶点j，若j未被访问过，则访问它，并将顶点j的访问标记置为已访问过，即visited[j]=1，再从j开始重复此过程。若j已访问，再看与顶点i有边相连的其他顶点，若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复前过程，直到图中所有顶点都被访问完为止。

以图1中无向图G为例可以得到不同深度优先搜索遍历顶点序列。

例如 ： 01374256

01473265

2 广度优先搜索遍历

假定给定图G的初态是所有顶点未被访问，在G中任选一顶点i作为遍历的起始点，则广度优先搜索遍历的基本思想是：

首先访问起始点i,并将其访问标记置为已访问过，既visited[i]=1,接着依次访问顶点i的未被访问过的邻接点w1、w2、……、wt，然后再依次访问与w1、w2、……、wt相邻接的未被访问过的顶点，依次类推，直到图中所有顶点都被访问完为止。

同样以图1中无向图G为例可得出不同的广度优先搜索遍历序列：

例如 ：01234567

02165437

3 图的存储结构数据类型的定义

为了讨论方便，下面用C语言来描述

1)图的邻接矩阵数据类型描述：

#definevexnummaxver

#defineedgenummaxedge

typedefstruct { int vertex[vexnum]; int matvix[vexnum] [vexnum];}adjmatrix;

2)图的邻接表数据类型描述：

typedefstructacrnode{intadjvex; structacrnode*nextedge;}edgenode;

typedefstructvnode{intdata; edgenode*firstedge; }vexnode;

typedefstruct{ vexnode vx[vexnum]; }adjlist；

4 深度优先搜索遍历算法

4.1 用邻接矩阵实现图的深度优先搜索

1)深度优先搜索遍历递归算法[2]

voiddfsm( int i)

{int j; G=&g; printf(“%3d”,G->vextex[i]); vixited[i]=1;

for(j=0;jmatrix[i][j]= =1&&(!visited[j])) dfsm(j);}

voidmdfs( )

{intk;for(k=0;k

用上述算法和图(b)的存储结构，可以描述从顶点0出发的深度优先搜索遍历顶点序列为：

01374256

2)深度优先搜索遍历非递归算法[1]

voiddfsm1( )

{int visited[vexnum];int stack[vexnum];int top=0, k, j;

for(k=0;k

for(k=0;k

while(top!=0)

{ i=stack[top];top--; if(visited[i]!=1) {visited[i]=1;printf(“%3d”,i); }

for(j=0;j

if(g.matrix[i][j]= =0&&visited[j]= =0){ top++;stack[top]=j;} } }}

用此算法得出的深度优先搜索遍历序列为：02651473

4.2 用邻接表实现图的深度优先搜索

1)深度优先搜索遍历递归算法[2][3]

void dfsL(int i){ edgenode *p; printf(“%3d”,g.vx[i].data); visited[i]=1; p=g.vx[i].firstedge;while(p!=NULL){ if(visited[p->adjvex]= =0) dfsL(p->adjvex); p=p->nextedge; } }

voidLdfs( ){ intk; for(k=0;k

用上述算法和图(c)的存储结构，可以描述从顶点0出发搜索遍历的顶点序列为：

01374256

2)深度优先搜索遍历非递归算法[1]

voiddfsL1()

{ edgenode*p; int visited[vexnum]={0}; int stack[vexnum]; int top=0, i,j;

for(i=0;i