數(shù)據(jù)結(jié)構(gòu)中鄰接圖的深度遍歷非遞歸算法（C++）

王偉業(yè) 路宇 李曉寒

摘要：在數(shù)據(jù)結(jié)構(gòu)課中，鄰接圖的深度遍歷往往采用遞歸算法，但遞歸算法有時(shí)存在后臺(tái)程序過多，導(dǎo)致運(yùn)行慢的缺點(diǎn)。為了解決這一問題，下面給出鄰接圖的深度遍歷的非遞歸算法（C++）。

關(guān)鍵詞：鄰接圖 深度遍歷 非遞歸

一、結(jié)構(gòu)體定義

圖采用鄰接表的形式存儲(chǔ)，分為頂點(diǎn)表和邊表，具體定義如下：

struct ArcNode ? ?//定義邊表節(jié)點(diǎn)

{

int adjvex; ? ? //臨界點(diǎn)域

ArcNode *next;

};

template

struct ?VertexNode ?//定義頂點(diǎn)表節(jié)點(diǎn)

{

DataType vertex;

ArcNode *firstedge;

};

二、算法描述

首先，引入棧stack[ ]，數(shù)組visited[ ]，該數(shù)組對于節(jié)點(diǎn)i，若i已被訪問，則visited[i]=1;若i還沒被訪問過，則visited[i]=0。頂點(diǎn)v開始，將v輸出并入棧，且將visited[v]設(shè)為1，然后通過兩層while循環(huán)，深度遍歷整個(gè)圖。

三、算法實(shí)現(xiàn)

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--;

}

}

四、算法總結(jié)

該算法利用了雙層的while循環(huán)，從而達(dá)到了遞歸算法的效果，雖代碼長度比遞歸算法長，但優(yōu)化了算法的運(yùn)行速度，更適合點(diǎn)集很大的圖使用。