摘要：在数据结构课中，邻接图的深度遍历往往采用递归算法，但递归算法有时存在后台程序过多，导致运行慢的缺点。为了解决这一问题，下面给出邻接图的深度遍历的非递归算法（C++）。
　　关键词：邻接图 深度遍历 非递归
　　一、结构体定义
　　图采用邻接表的形式存储，分为顶点表和边表，具体定义如下：
　　struct ArcNode    //定义边表节点
　　{
　　 int adjvex;     //临界点域
　　 ArcNode *next;
　　};
　　template <class DataType>
　　struct  VertexNode  //定义顶点表节点
　　{
　　 DataType vertex;
　　 ArcNode *firstedge;
　　};
　　二、算法描述
　　首先，引入栈stack[ ]，数组visited[ ]，该数组对于节点i，若i已被访问，则visited[i]=1;若i还没被访问过，则visited[i]=0。顶点v开始，将v输出并入栈，且将visited[v]设为1，然后通过两层while循环，深度遍历整个图。
　　三、算法实现
　　template<class DataType>
　　void MGraph<DataType> ：：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<<t;
　　 stack[++top]=t;
　　 break;
　　 }
　　else p=p->next;
　　}
　　if（p==NULL）  top--;
　　 }
　　}
　　四、算法總结
　　该算法利用了双层的while循环，从而达到了递归算法的效果，虽代码长度比递归算法长，但优化了算法的运行速度，更适合点集很大的图使用。