一：圖的遍歷——深度優(yōu)先搜索

在本文其他內(nèi)容中只是大體概括了主要的圖論內(nèi)容，更加詳細(xì)的代碼實(shí)現(xiàn)及算法分析在此給出。

?

深度優(yōu)先搜索（DFS）類(lèi)似樹(shù)的先序遍歷。

假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問(wèn)，則深度優(yōu)先搜索可從圖中某個(gè)頂點(diǎn)發(fā)，訪問(wèn)此頂點(diǎn),然后依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中階和V有路徑相通的頂點(diǎn)都被訪問(wèn)到;若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。

以下圖為例，假設(shè)從V1出發(fā)開(kāi)始搜索，在訪問(wèn)了V1之后選擇鄰接點(diǎn)V2，因?yàn)閂2未被訪問(wèn)，

則從V2出發(fā)進(jìn)行搜索。依次類(lèi)推,接著從V4\V8V5出發(fā)進(jìn)行搜索。在訪問(wèn)了V5之后，由于V5的鄰接點(diǎn)都已被訪問(wèn)，則搜索回到V1。此時(shí)由于V1的另一個(gè)鄰接點(diǎn)未被訪問(wèn)，則搜索又從V1到V3，再繼續(xù)進(jìn)行下去。由此，得到的頂點(diǎn)訪問(wèn)序列為:

V1->V2->V4->V8->V5->V3->V6->V7;
顯然，這是一個(gè)遞歸的過(guò)程。為了在遍歷過(guò)程中便于區(qū)分頂點(diǎn)是否已被訪問(wèn)需附設(shè)訪問(wèn)標(biāo)志數(shù)組visited[n-1]其初值為false一?且某個(gè)頂點(diǎn)被訪問(wèn)，則其相應(yīng)的分量置"true"。

?

?

具體代碼用C語(yǔ)言實(shí)現(xiàn)如下：

#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等 */#include<limits.h> /* INT_MAX等 */#include<stdio.h> /* EOF(=^Z或F6),NULL */#include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */#include<process.h> /* exit() *//* 函數(shù)結(jié)果狀態(tài)代碼 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; /* Status是函數(shù)的類(lèi)型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */typedef int Boolean; /* Boolean是布爾類(lèi)型,其值是TRUE或FALSE */#define MAX_NAME 5 /* 頂點(diǎn)字符串的最大長(zhǎng)度 */typedef int InfoType;typedef char VertexType[MAX_NAME]; /* 字符串類(lèi)型 *//* 圖的鄰接表存儲(chǔ)表示 */#define MAX_VERTEX_NUM 20typedef enum{DG,DN,AG,AN}GraphKind; /* {有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)} */typedef struct ArcNode{int adjvex; /* 該弧所指向的頂點(diǎn)的位置 */struct ArcNode *nextarc; /* 指向下一條弧的指針 */InfoType *info; /* 網(wǎng)的權(quán)值指針） */}ArcNode; /* 表結(jié)點(diǎn) */typedef struct{VertexType data; /* 頂點(diǎn)信息 */ArcNode *firstarc; /* 第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針 */}VNode,AdjList[MAX_VERTEX_NUM]; /* 頭結(jié)點(diǎn) */typedef struct{AdjList vertices;int vexnum,arcnum; /* 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) */int kind; /* 圖的種類(lèi)標(biāo)志 */}ALGraph;Boolean visited[MAX_VERTEX_NUM]; /* 訪問(wèn)標(biāo)志數(shù)組(全局量) */void(*VisitFunc)(char* v); /* 函數(shù)變量(全局量) */void DFS(ALGraph G,int v){ /* 從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。算法7.5 */int w;VertexType v1,w1;strcpy(v1,*GetVex(G,v));visited[v]=TRUE; /* 設(shè)置訪問(wèn)標(biāo)志為T(mén)RUE(已訪問(wèn)) */VisitFunc(G.vertices[v].data); /* 訪問(wèn)第v個(gè)頂點(diǎn) */for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))if(!visited[w])DFS(G,w); /* 對(duì)v的尚未訪問(wèn)的鄰接點(diǎn)w遞歸調(diào)用DFS */}void DFSTraverse(ALGraph G,void(*Visit)(char*)){ /* 對(duì)圖G作深度優(yōu)先遍歷。算法7.4 */int v;VisitFunc=Visit; /* 使用全局變量VisitFunc,使DFS不必設(shè)函數(shù)指針參數(shù) */for(v=0;v<G.vexnum;v++)visited[v]=FALSE; /* 訪問(wèn)標(biāo)志數(shù)組初始化 */for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v); /* 對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFS */printf("\n");}

?

?

?

?

二：廣度優(yōu)先搜索

廣度優(yōu)先搜索(BFS)遍歷類(lèi)似于樹(shù)的層序遍歷。

假設(shè)從圖中某頂點(diǎn)V出發(fā)，在訪問(wèn)了V之后依次訪問(wèn)V的未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)并使“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn),重復(fù)上述過(guò)程,直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。換句話說(shuō)廣度優(yōu)先搜索遍歷圖的過(guò)程是以V為起始點(diǎn)，由近至遠(yuǎn).依次訪問(wèn)和V有路徑相通且路徑長(zhǎng)度為1，2，...的頂點(diǎn)。
對(duì)上圖得到的頂點(diǎn)訪問(wèn)序列為V1->V2->V3->V4->V5->V6->V7->v8。?

具體代碼用C語(yǔ)言實(shí)現(xiàn)如下：

typedef int QElemType; /* 隊(duì)列類(lèi)型 *//* c3-2.h 單鏈隊(duì)列－－隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) */typedef struct QNode{QElemType data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front,rear; /* 隊(duì)頭、隊(duì)尾指針 */}LinkQueue; /* bo3-2.c 鏈隊(duì)列(存儲(chǔ)結(jié)構(gòu)由c3-2.h定義)的基本操作(9個(gè)) */Status InitQueue(LinkQueue *Q){ /* 構(gòu)造一個(gè)空隊(duì)列Q */(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));if(!(*Q).front)exit(OVERFLOW);(*Q).front->next=NULL;return OK;}Status DestroyQueue(LinkQueue *Q){ /* 銷(xiāo)毀隊(duì)列Q(無(wú)論空否均可) */while((*Q).front){(*Q).rear=(*Q).front->next;free((*Q).front);(*Q).front=(*Q).rear;}return OK;}Status ClearQueue(LinkQueue *Q){ /* 將Q清為空隊(duì)列 */QueuePtr p,q;(*Q).rear=(*Q).front;p=(*Q).front->next;(*Q).front->next=NULL;while(p){q=p;p=p->next;free(q);}return OK;}Status QueueEmpty(LinkQueue Q){ /* 若Q為空隊(duì)列,則返回TRUE,否則返回FALSE */if(Q.front==Q.rear)return TRUE;elsereturn FALSE;}int QueueLength(LinkQueue Q){ /* 求隊(duì)列的長(zhǎng)度 */int i=0;QueuePtr p;p=Q.front;while(Q.rear!=p){i++;p=p->next;}return i;}Status GetHead_Q(LinkQueue Q,QElemType *e) /* 避免與bo2-6.c重名 */{ /* 若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR */QueuePtr p;if(Q.front==Q.rear)return ERROR;p=Q.front->next;*e=p->data;return OK;}Status EnQueue(LinkQueue *Q,QElemType e){ /* 插入元素e為Q的新的隊(duì)尾元素 */QueuePtr p=(QueuePtr)malloc(sizeof(QNode));if(!p) /* 存儲(chǔ)分配失敗 */exit(OVERFLOW);p->data=e;p->next=NULL;(*Q).rear->next=p;(*Q).rear=p;return OK;}Status DeQueue(LinkQueue *Q,QElemType *e){ /* 若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR */QueuePtr p;if((*Q).front==(*Q).rear)return ERROR;p=(*Q).front->next;*e=p->data;(*Q).front->next=p->next;if((*Q).rear==p)(*Q).rear=(*Q).front;free(p);return OK;}Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType)){ /* 從隊(duì)頭到隊(duì)尾依次對(duì)隊(duì)列Q中每個(gè)元素調(diào)用函數(shù)vi()。一旦vi失敗,則操作失敗 */QueuePtr p;p=Q.front->next;while(p){vi(p->data);p=p->next;}printf("\n");return OK;}void BFSTraverse(ALGraph G,void(*Visit)(char*)){/*按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問(wèn)標(biāo)志數(shù)組visited。算法7.6 */int v,u,w;VertexType u1,w1;LinkQueue Q;for(v=0;v<G.vexnum;++v)visited[v]=FALSE; /* 置初值 */InitQueue(&Q); /* 置空的輔助隊(duì)列Q */for(v=0;v<G.vexnum;v++) /* 如果是連通圖,只v=0就遍歷全圖 */if(!visited[v]) /* v尚未訪問(wèn) */{visited[v]=TRUE;Visit(G.vertices[v].data);EnQueue(&Q,v); /* v入隊(duì)列 */while(!QueueEmpty(Q)) /* 隊(duì)列不空 */{DeQueue(&Q,&u); /* 隊(duì)頭元素出隊(duì)并置為u */strcpy(u1,*GetVex(G,u));for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))if(!visited[w]) /* w為u的尚未訪問(wèn)的鄰接頂點(diǎn) */{visited[w]=TRUE;Visit(G.vertices[w].data);EnQueue(&Q,w); /* w入隊(duì) */}}}printf("\n");}

歡迎關(guān)注本博主
?

總結(jié)

以上是生活随笔為你收集整理的图的遍历——深度优先搜索+广度优先搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。