廣度優(yōu)先搜素（BFS）

廣度優(yōu)先搜索(又稱(chēng)寬度優(yōu)先搜索)算法是最簡(jiǎn)便的圖的搜索算法之一，該算法屬于一種盲目搜尋法，目的是系統(tǒng)地展開(kāi)并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說(shuō)，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。

廣度優(yōu)先搜素也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹(shù)算法都采用了和寬度優(yōu)先搜索類(lèi)似的思想。

廣度優(yōu)先搜素類(lèi)似于樹(shù)的層次遍歷，遍歷結(jié)果不唯一
我們依據(jù)鄰接表進(jìn)行遍歷，還需要借助到鏈隊(duì)的內(nèi)容。

以如下連通圖為例：

構(gòu)建其對(duì)應(yīng)的鄰接表：

采用廣度優(yōu)先搜素的遍歷順序如下：

程序運(yùn)行時(shí)并非運(yùn)行到這里就結(jié)束了，而是會(huì)繼續(xù)遍歷，只是進(jìn)行判斷的時(shí)候visit[i]數(shù)組已經(jīng)置為1，不需要繼續(xù)輸出了。
注：為了標(biāo)定一個(gè)·頂點(diǎn)是否被遍歷過(guò)了，需要采用輔助數(shù)組visit[i]進(jìn)行判定，沒(méi)當(dāng)頂點(diǎn)被遍歷則將其對(duì)應(yīng)的visit[i]置為1，避免重讀。

---

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

從某一頂點(diǎn)出發(fā)進(jìn)行訪問(wèn)，該點(diǎn)首先被讀入，visit[i]置為1

依次訪問(wèn)該點(diǎn)的鄰接點(diǎn)，將其加入隊(duì)列

對(duì)每個(gè)鄰接點(diǎn)的鄰接點(diǎn)進(jìn)行入隊(duì)操作

注意：“先訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”應(yīng)先于“后訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”
這也是為什么要采用隊(duì)列這種結(jié)構(gòu)存儲(chǔ)的原因：我們需要保證在一次遍歷中記錄下某一點(diǎn)的全部鄰接點(diǎn)，但是每個(gè)點(diǎn)卻又對(duì)應(yīng)著自己的鄰接點(diǎn)，根據(jù)廣度優(yōu)先搜索的要求，我們需要保證“先訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”應(yīng)先于“后訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”，所以隊(duì)列是個(gè)不錯(cuò)的輔助工具。我們根據(jù)隊(duì)列的順序就可以找出對(duì)應(yīng)鄰接點(diǎn)的位置，進(jìn)而確定它所對(duì)應(yīng)的鄰接點(diǎn)。

隊(duì)列變化：

注：紅線劃去的代表該頂點(diǎn)的visit[i]=1，無(wú)需多次加入隊(duì)列。

廣度優(yōu)先搜索函數(shù)代碼：

void BFSTraverse(AdjMatrix *G)//廣度優(yōu)先搜索 {LinkQueue Q;for(int v=0;v<G->n;++v) visited[v]=false;InitQueue(&Q);printf("廣度優(yōu)先搜索順序");for(int v=0;v<G->n;++v){if(!visited[v]){EnQueue(&Q,v);//將鄰接表的頂點(diǎn)元素入隊(duì) while(!QueueEmpty(&Q)){int u; DeQueue(&Q,u);if(!visited[u]) {visited[u]=true;printf("->%c",G->adjlist[u].vertex);} //對(duì)該頂點(diǎn)元素的邊關(guān)系進(jìn)行遍歷，依次入隊(duì) for(EdgeNode *w=G->adjlist[u].edgenext;w;w=w->next)if(!visited[w->adjvex]) EnQueue(&Q,w->adjvex);}printf("\n\n"); }} }

具體代碼如下：

#include <stdio.h> #include <stdlib.h> #define MaxVertices 100 #define MAX_VERTEX_NUM 20 typedef struct node{ //邊表 int adjvex;node* next; }EdgeNode; typedef struct{ //頂點(diǎn)表 int vertex; EdgeNode* edgenext; }VertexNode; typedef VertexNode AdjList[MaxVertices]; typedef struct{ AdjList adjlist; int n,e; }AdjMatrix; typedef struct Qnode{ //鏈隊(duì)結(jié)點(diǎn)的類(lèi)型int data;struct Qnode *next; }Qnode,*QueuePtr; typedef struct{ //鏈隊(duì)指針類(lèi)型QueuePtr front;QueuePtr rear; }LinkQueue; int visited[MAX_VERTEX_NUM]; void InitQueue(LinkQueue *Q)//初始化鏈隊(duì) {Q->front=Q->rear=(QueuePtr)malloc(sizeof(Qnode));if(!Q->front) exit(1); //存儲(chǔ)分配失敗Q->front->next=NULL;} void EnQueue(LinkQueue *Q,int e)//入隊(duì) { QueuePtr p;p=(QueuePtr)malloc(sizeof(Qnode));p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p; } int QueueEmpty(LinkQueue *Q)//判斷隊(duì)空 {return(Q->front==Q->rear? 1:0); } void DeQueue(LinkQueue *Q,int &e)//出隊(duì) { QueuePtr p;if(QueueEmpty(Q)){printf("\n Queue is free!");exit(1);}//ifp=Q->front->next;e=p->data;Q->front->next=p->next;if(Q->front->next==NULL) Q->rear=Q->front;free(p);} void CreateGraph(AdjMatrix* G)//構(gòu)造圖 { int i,j,k,w,v; EdgeNode *s; printf("輸入頂點(diǎn)數(shù)和邊數(shù)（中間以空格分開(kāi)）："); scanf("%d%d",&G->n,&G->e); printf("建立頂點(diǎn)表\n"); for (i=0;i<G->n;i++) { //fflush(stdin); //如果 stream 指向輸入流（如 stdin），那么 fflush 函數(shù)的行為是不確定的。//故而使用 fflush(stdin) 是不正確的。getchar(); printf("請(qǐng)輸入第%d個(gè)頂點(diǎn)的信息:",i+1);G->adjlist[i].vertex=getchar();G->adjlist[i].edgenext=NULL; } //前插法 printf("建立邊表\n"); for (k=0;k<G->e;k++) { printf("輸入有連接的頂點(diǎn)序號(hào)："); scanf("%d%d",&i,&j); //對(duì)于直接相連的進(jìn)行編入(即對(duì)輸入“0 1”時(shí)，在0對(duì)應(yīng)的邊表中編入1) i-=1;j-=1; s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=j;//邊表賦值 s->next=G->adjlist[i].edgenext; G->adjlist[i].edgenext=s; //對(duì)于間接相連的進(jìn)行編入(即對(duì)輸入“0 1”時(shí)，在1對(duì)應(yīng)的邊表中編入0)s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=i; s->next=G->adjlist[j].edgenext; G->adjlist[j].edgenext=s; } } void DispGraph(AdjMatrix *G)//銷(xiāo)毀圖 {int i;for (i=0;i<G->n;i++) { printf("%d->",i+1); while(1) { if(G->adjlist[i].edgenext==NULL){printf("^");break; }printf("%d->",G->adjlist[i].edgenext->adjvex+1); G->adjlist[i].edgenext=G->adjlist[i].edgenext->next; } printf("\n"); } } void BFSTraverse(AdjMatrix *G)//廣度優(yōu)先搜索 {LinkQueue Q;for(int v=0;v<G->n;++v) visited[v]=false;InitQueue(&Q);printf("廣度優(yōu)先搜索順序");for(int v=0;v<G->n;++v){if(!visited[v]){EnQueue(&Q,v);//將鄰接表的頂點(diǎn)元素入隊(duì) while(!QueueEmpty(&Q)){int u; DeQueue(&Q,u);if(!visited[u]) {visited[u]=true;printf("->%c",G->adjlist[u].vertex);//visit一下} //對(duì)該頂點(diǎn)元素的邊關(guān)系進(jìn)行遍歷，依次入隊(duì) for(EdgeNode *w=G->adjlist[u].edgenext;w;w=w->next)if(!visited[w->adjvex]) EnQueue(&Q,w->adjvex);}printf("\n\n"); }} } int main() { //freopen("1.txt","r",stdin);AdjMatrix* G= (AdjMatrix*)malloc(sizeof(AdjMatrix)); CreateGraph(G);BFSTraverse(G); DispGraph(G); }

測(cè)試數(shù)據(jù)如下：
注：由于測(cè)試輸入數(shù)據(jù)較多，程序可以采用文件輸入

5 7
1
2
3
4
5
1 2
1 3
1 4
2 3
2 4
3 5
4 5

總結(jié)

以上是生活随笔為你收集整理的连通图遍历策略之广度优先搜索（C语言）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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