數據結構中圖的遍歷算法

摘要：本文根據圖的存儲結構、搜索路徑及編制算法的方法不同，詳盡地給出八種不同的圖的遍歷算法思想。即：從圖的鄰接矩陣和鄰接表兩種不同存儲結構，再考慮到遞歸和非遞歸兩種遍歷思想的不同，分別把深度優先搜索遍歷和廣度優先搜索遍歷分為四種不同的遍歷方法。其目的是：通過本文的討論，使初學者及高職學生能充分掌握數據結構中圖的不同遍歷算法并能正確的給出圖的各種遍歷程序。

關鍵詞：圖；存儲結構；算法

中圖分類號：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為例可以得到不同深度優先搜索遍歷頂點序列。

例如 ： 0→1→3→7→4→2→5→6

0→1→4→7→3→2→6→5

2 廣度優先搜索遍歷

假定給定圖G的初態是所有頂點未被訪問，在G中任選一頂點i作為遍歷的起始點，則廣度優先搜索遍歷的基本思想是：

首先訪問起始點i，并將其訪問標記置為已訪問過，既visited[i]=1，接著依次訪問頂點i的未被訪問過的鄰接點w1、w2、……、wt，然后再依次訪問與w1、w2、……、wt相鄰接的未被訪問過的頂點，依次類推，直到圖中所有頂點都被訪問完為止。

同樣以圖1中無向圖G為例可得出不同的廣度優先搜索遍歷序列：

例如 ：0→1→2→3→4→5→6→7

0→2→1→6→5→4→3→7

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出發的深度優先搜索遍歷頂點序列為：

0→1→3→7→4→2→5→6

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]= =0visited[j]= =0){ top++;stack[top]=j;} } }}

用此算法得出的深度優先搜索遍歷序列為：0→2→6→5→1→4→7→3

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出發搜索遍歷的頂點序列為：

0→1→3→7→4→2→5→6

2)深度優先搜索遍歷非遞歸算法[1]

voiddfsL1()

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

for(i=0;i

while(top!=0) {j=stack[top]; top--; if(visited[j]!=1) {visited[j]=1;printf(“%3d”，j);}

for(p=g.vx[j].firstedge;p!=NULL;p=p->nextedge)

if(visited[p->adjvex]= =0){ top++;stack[top]=p->adjvex; } } }}}

5 廣度優先搜索遍歷算法

5.1 用鄰接矩陣實現圖的廣度優先搜索

1)廣度優先搜索遍歷遞歸算法[2][3]

voidbfsm( )

{ inti;intq[vexnum+1]; intfront=0; intrear=0;

for(i=0;i

voidmbfs( )

{int j，i; while(rear!=front) {front++;i=q[front]; if(visited[i]= =0) { visited[i]=1; printf(“%3d”，i);}

for(j=0;jmatrix[i][j]= =1(!visited[j])) { rear++;q[rear]=j; } } }

2)廣度優先搜索遍歷非遞歸算法和深度優先搜索遍歷非遞歸算法相似，不同之處在于前者用棧存儲數據，后者用隊列儲數據。

5.2 用鄰接表實現圖的廣度優先搜索

1)廣度優先搜索遍歷遞歸算法

voidbfsL( )

{ int i; for(i=0;i

{ if(visited[i]= =0) {rear++; q[rear]=i;}Lbfs(); } }

void Lbfs( )

{ intj;edgenode *p;while(front!=rear) { front++; j=q[front];

if(visited[j]= =0) {visited[j]=1; printf(“%3d”，j);}

for(p=g.vx[j].firstedge;p!=NULL;p=p->nextedge)

{ if(visited[p->adjvex]= =0) { rear++; q[rear]=p->adjvex; } } Lbfs( ); } }

2)廣度優先搜索遍歷非遞歸算法[1][3]

voidbfsL1( )

{ edgenode *p; int q[vexnum];int front=-1; int rear=-1; int visited[vexnum]={0};

for(i=0;i

while(front!=rear) {front++;j=q[front]; if(visited[j]!=1) {visited[j]=1;printf(“%3d”，j);}

for(p=g.vx[j].firstedge;p!=NULL;p=p->nextedge)

if(visited[p->adjvex]= =0) { rear++;[rear]=p->adjvex;} } } }}

參考文獻：

[1] 楊棖.數據結構[M].高等教育出版社，2002.

[2] 嚴蔚敏，吳偉民.數據結構[M].清華大學出版社，1997.

[3] 李根強.數據結構[M].中國水科水電出版社，2001.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文