廣度優(yōu)先算法

1、計(jì)算機(jī)算法的設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告廣度優(yōu)先算法1、 描述 廣度優(yōu)先搜索,即BFS(Breadth First Search)，是一種相當(dāng)常用的圖算法，其特點(diǎn)是：每次搜索指定點(diǎn)，并將其所有未訪問(wèn)過(guò)的鄰近節(jié)點(diǎn)加入搜索隊(duì)列，循環(huán)搜索過(guò)程直到隊(duì)列為空。算法描述如下： （1）將起始節(jié)點(diǎn)放入隊(duì)列尾部（2）While(隊(duì)列不為空） 取得并刪除隊(duì)列首節(jié)點(diǎn)Node 處理該節(jié)點(diǎn)Node 把Node的未處理相鄰節(jié)點(diǎn)加入隊(duì)列尾部2、 代碼#include "stdafx.h"#include<iostream.h>/構(gòu)造有向圖p162,無(wú)向圖p168#include<string.h

2、>#include<iomanip.h>#include<stdlib.h>/包含exit函數(shù)/廣度優(yōu)先#define Null 0/廣度優(yōu)先#define INFINITY 10000/最大值,無(wú)窮#define MAX_VERTEX_NUM 20/最大頂點(diǎn)個(gè)數(shù),即可以計(jì)算的最大規(guī)模typedef struct ArcCell float adj;/無(wú)權(quán)圖為1或0,有權(quán)圖為權(quán)重 char info30;/該弧相關(guān)信息ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_

3、VERTEX_NUM20;/頂點(diǎn)向量,如v1,v2,.等 AdjMatrix arcs; int vexnum,arcnum;MGraph;/廣度優(yōu)先typedef struct QNode int data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/隊(duì)頭指針 QueuePtr rear;/隊(duì)尾指針LinkQueue;/廣度優(yōu)先int LocateVex(MGraph G,char *v) int i,num=-1; for(i=0;i<G.vexnum;i+) if(strcmp(v,G.vex

4、si)=0)/相等時(shí)為0,大于為正,小于為負(fù) num=i; break; if(num<0) cout<<"沒(méi)有匹配的頂點(diǎn),輸入錯(cuò)誤!"<<endl; return -1; else return num;void CreateNet(MGraph &G) int i,j,k,s=0; int IncInfo=-1;/IncInfo為0則各弧不含其它信息,有信息則為其他數(shù)字 char v220;/存放一條邊的兩個(gè)頂點(diǎn) char *p; float w;/輸入的權(quán)重 int direct=-1;/有向圖為1,無(wú)向圖為其他數(shù)字 /char

5、temp10020;/這個(gè)temp不能放到本函數(shù)內(nèi),or,G.vexsi引用他時(shí),賦了值,跳出這個(gè)函數(shù)就沒(méi)有值.這樣不好 /scanf(&G.vexnum,&G.arcnum,&IncInfo); cout<<"構(gòu)建有向圖請(qǐng)輸入數(shù)字1,構(gòu)建無(wú)向圖請(qǐng)輸入其他數(shù)字(無(wú)向圖請(qǐng)輸入上三角的邊)."<<endl; cin>>direct; cout<<"各頂點(diǎn)無(wú)信息則輸入數(shù)字0,有信息輸入其他數(shù)字."<<endl; cin>>IncInfo; cout<<&

6、quot;請(qǐng)輸入頂點(diǎn)和弧數(shù)目:"<<endl; cin>>G.vexnum>>G.arcnum; cout<<"請(qǐng)輸入"<<G.vexnum<<"個(gè)頂點(diǎn)的符號(hào),如v1,v2."<<endl; for(i=0;i<G.vexnum;+i) p=G.vexsi; cin>>p;/注意vexsMAX_VERTEX_NUM中的MAX_VERTEX_NUM大于G.vexnum for(i=0;i<G.vexnum;i+) cout<<G

7、.vexsi<<" " for(i=0;i<G.vexnum;+i) for(j=0;j<G.vexnum;+j) G.arcsij.adj=INFINITY; p=G.; p='0'/問(wèn)題 for(k=0;k<G.arcnum;+k)/循環(huán)弧的次數(shù) cout<<"第"<<k+1<<"次輸入:"<<endl; cout<<"出發(fā)點(diǎn):" p=v0; cin>>p; i=Locat

8、eVex(G,p); cout<<"接受點(diǎn):" p=v1; cin>>p; j=LocateVex(G,p); cout<<"權(quán)重:" cin>>w;/輸入格式: v1 v2 18 cout<<"i="<<i<<" j="<<j<<endl; G.arcsij.adj=w; if(IncInfo) cout<<"輸入信息:" p=G.; cin>&g

9、t;p; if(direct!=1) G.arcsji=G.arcsij; cout<<"頂點(diǎn)數(shù)是:"<<G.vexnum<<endl; cout<<"弧數(shù)是:"<<G.arcnum<<endl; cout<<"各頂點(diǎn)分別是:" for(i=0;i<G.vexnum;i+) cout<<G.vexsi<<" " cout<<endl; for(i=0;i<G.vexnum;i+) fo

10、r(j=0;j<G.vexnum;j+) cout<<setw(8)<<G.arcsij.adj; if(IncInfo) if(G.arcsij.adj!=INFINITY) cout<<setw(6)<<G.; else cout<<setw(6)<<" " cout<<endl; /廣度優(yōu)先bool visited100;/隨便設(shè)置一百個(gè)布爾值void InitQueue(LinkQueue &Q) Q.front=Q.rear=(QueuePtr)

11、malloc(sizeof(QNode); if(!Q.front) exit(-1); Q.front->next=Null;void EnQueue(LinkQueue &Q,int e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(-1); p->data=e; p->next=Null; Q.rear->next=p; Q.rear=p;void DeQueue(LinkQueue &Q,int &e) QueuePtr p; if(Q.front=Q.rear) c

12、out<<"隊(duì)頭等于隊(duì)尾!"<<endl; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.front; free(p);int QueueEmpty(LinkQueue &Q) if(Q.front=Q.rear) return 1; else return 0;void visit(MGraph G,int v) cout<<"訪問(wèn)了第"<<v<<"個(gè)頂

13、點(diǎn)"<<endl; cout<<"即"<<G.vexsv<<"頂點(diǎn)"<<endl;int FirstAdjVex(MGraph G,int v) int i,num=-1; for(i=0;i<G.vexnum;i+) if(G.arcsvi.adj!=INFINITY) num=i; break; return num;int NextAdjVex(MGraph G,int v,int w) int i,num=-1; for(i=w+1;i<G.vexnum;i+) i

14、f(G.arcsvi.adj!=INFINITY) num=i; break; return num;void BFSTraverse(MGraph G) int v; int u;/出隊(duì)元素 int w; LinkQueue Q; for(v=0;v<G.vexnum;v+) visitedv=0; InitQueue(Q); for(v=0;v<G.vexnum;v+) if(!visitedv) visitedv=1; visit(G,v); EnQueue(Q,v); while(!QueueEmpty(Q) DeQueue(Q,u); for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w) if(!visitedw) visitedw=1; visit(G,w); EnQueue(Q,w); /廣度優(yōu)先void main() MGraph G; CreateNet(G); /這時(shí)上面已經(jīng)求出G.vexn