數據結構中鄰接圖的深度遍歷非遞歸算法（C++）

王偉業 路宇 李曉寒

摘要：在數據結構課中，鄰接圖的深度遍歷往往采用遞歸算法，但遞歸算法有時存在后臺程序過多，導致運行慢的缺點。為了解決這一問題，下面給出鄰接圖的深度遍歷的非遞歸算法（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循環，從而達到了遞歸算法的效果，雖代碼長度比遞歸算法長，但優化了算法的運行速度，更適合點集很大的圖使用。