王伟业 路宇 李晓寒

摘要：在数据结构课中，邻接图的深度遍历往往采用递归算法，但递归算法有时存在后台程序过多，导致运行慢的缺点。为了解决这一问题，下面给出邻接图的深度遍历的非递归算法（C++）。

关键词：邻接图 深度遍历 非递归

一、结构体定义

图采用邻接表的形式存储，分为顶点表和边表，具体定义如下：

struct ArcNode    //定义边表节点

{

int adjvex;     //临界点域

ArcNode *next;

};

template

struct  VertexNode  //定义顶点表节点

{

DataType vertex;

ArcNode *firstedge;

};

二、算法描述

首先，引入栈stack[ ]，数组visited[ ]，该数组对于节点i，若i已被访问，则visited[i]=1;若i还没被访问过，则visited[i]=0。顶点v开始，将v输出并入栈，且将visited[v]设为1，然后通过两层while循环，深度遍历整个图。

三、算法实现

template

void MGraph ：：DFSTraverse（int v）

{

cout << adjlist[v].vertex;

visited[v]=1;

top=-1;

s[++top]=v;

while（top！=-1）

{

i=stack[top];

p=adjlist[i].firstedge;

while（p！=NULL）

{

t=p->adjvex;

if（visited[t]==0）

{

visited[v]=1;

cout<

stack[++top]=t;

break;

}

else p=p->next;

}

if（p==NULL）  top--;

}

}

四、算法總结

该算法利用了双层的while循环，从而达到了递归算法的效果，虽代码长度比递归算法长，但优化了算法的运行速度，更适合点集很大的图使用。