首页 > 代码库 > 如何实现广度优先遍历(BFS)
如何实现广度优先遍历(BFS)
BFS过程:
一:访问顶点V,并标记V为已经访问
二:顶点V入队列
三:如果队列非空,进行执行,否则算法结束
四:出队列取得对头顶点u,如果顶点未被访问,就访问该顶点,并标记该顶点为已经访问
五:查找u的第一个邻接节点w
六:如果w不存在,则转到步骤三,否则循环执行
a. 如果w没有被访问过,则先把w入队列
b.查找顶点u的下一个邻接节点,记为w,并转到步骤六
上图使用BFS访问顺序为:
A BEDC
队列的变化过程如下:
A
B
BE
ED
D
C
代码如下:
#include<iostream> using namespace std; #define VertexSize 10 int visit[VertexSize]; //=================================== #define QueueSize 30 typedef struct { int Seq[QueueSize]; int front; int rear; int count; }RQueue; RQueue Q; void Initiate_Queue(RQueue *Q) { Q->front=0; Q->rear=0; Q->count=0; } void AppendQueue(RQueue *Q,int data) { if(Q->count>=QueueSize) { cout<<"overflow"<<endl; return ; } Q->Seq[Q->rear]=data; Q->rear=(Q->rear+1)%QueueSize; Q->count++; } int QueueNotEmpty(RQueue *Q) { if(Q->count!=0) return 1; else return 0; } int DeleteQueue(RQueue *Q) { if(Q->count<=0) { cout<<"empty"<<endl; return NULL; } int d; d=Q->Seq[Q->front]; Q->front=(Q->front+1)%QueueSize; Q->count--; return d; } //=================================== typedef struct { int weight[VertexSize][VertexSize]; }Graph; void Initiate_Graph(Graph *g,int n) { int i,j; for(i=0;i<n;i++) visit[i]=0; for(j=0;j<n;j++) { if(i==j) g->weight[i][j]=0; else g->weight[i][j]=0x7fff; } } void InsertEdge(Graph *g,int v,int w,int weight,int n) { if(v<0 || v>=n||w<0||w>=n) { cout<<"overflow!========="<<endl; } g->weight[v][w]=weight; } void dfs(Graph *g,int u,int n) { cout<<u<<" "; visit[u]=1; int i; for(i=0;i<n;i++) { if(g->weight[u][i]>0 && g->weight[u][i]<0x7fff && !visit[i]) { visit[i]=1; dfs(g,i,n); } } } void bfs(Graph *g,int u,int n) { Initiate_Queue(&Q); int j; cout<<u<<" "; visit[u]=1; AppendQueue(&Q,u); while(QueueNotEmpty(&Q)) { int x=DeleteQueue(&Q); for(j=0;j<n;j++) { if(g->weight[x][j]>0 &&g->weight[x][j]<0x7fff && !visit[j]) { cout<<j<<" "; visit[j]=1; AppendQueue(&Q,j); } } } } void main() { Graph g; int n,edge; cout<<"请输入图的顶点个数:"<<endl; cin>>n; cout<<"请输入图的边个数"<<endl; cin>>edge; Initiate_Graph(&g,n); int i,p1,p2,weight; cout<<"请输入顶点-顶点-权值:"<<endl; for(i=0;i<edge;i++) { cin>>p1>>p2>>weight; InsertEdge(&g,p1,p2,weight,n); } cout<<"深度优先遍历为:"<<endl; dfs(&g,0,n); cout<<endl; for(i=0;i<n;i++) visit[i]=0; cout<<"广度优先遍历为:"<<endl; bfs(&g,0,n); cout<<endl; system("pause"); }
如何实现广度优先遍历(BFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。