广度优先算法

1、计算机算法的设计与分析实验报告广度优先算法1、 描述 广度优先搜索,即BFS(Breadth First Search)，是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的邻近节点加入搜索队列，循环搜索过程直到队列为空。算法描述如下： （1）将起始节点放入队列尾部（2）While(队列不为空） 取得并删除队列首节点Node 处理该节点Node 把Node的未处理相邻节点加入队列尾部2、 代码#include "stdafx.h"#include<iostream.h>/构造有向图p162,无向图p168#include<string.h

2、>#include<iomanip.h>#include<stdlib.h>/包含exit函数/广度优先#define Null 0/广度优先#define INFINITY 10000/最大值,无穷#define MAX_VERTEX_NUM 20/最大顶点个数,即可以计算的最大规模typedef struct ArcCell float adj;/无权图为1或0,有权图为权重 char info30;/该弧相关信息ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_

3、VERTEX_NUM20;/顶点向量,如v1,v2,.等 AdjMatrix arcs; int vexnum,arcnum;MGraph;/广度优先typedef struct QNode int data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针LinkQueue;/广度优先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)/相等时为0,大于为正,小于为负 num=i; break; if(num<0) cout<<"没有匹配的顶点,输入错误!"<<endl; return -1; else return num;void CreateNet(MGraph &G) int i,j,k,s=0; int IncInfo=-1;/IncInfo为0则各弧不含其它信息,有信息则为其他数字 char v220;/存放一条边的两个顶点 char *p; float w;/输入的权重 int direct=-1;/有向图为1,无向图为其他数字 /char

5、temp10020;/这个temp不能放到本函数内,or,G.vexsi引用他时,赋了值,跳出这个函数就没有值.这样不好 /scanf(&G.vexnum,&G.arcnum,&IncInfo); cout<<"构建有向图请输入数字1,构建无向图请输入其他数字(无向图请输入上三角的边)."<<endl; cin>>direct; cout<<"各顶点无信息则输入数字0,有信息输入其他数字."<<endl; cin>>IncInfo; cout<<&

6、quot;请输入顶点和弧数目:"<<endl; cin>>G.vexnum>>G.arcnum; cout<<"请输入"<<G.vexnum<<"个顶点的符号,如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'/问题 for(k=0;k<G.arcnum;+k)/循环弧的次数 cout<<"第"<<k+1<<"次输入:"<<endl; cout<<"出发点:" p=v0; cin>>p; i=Locat

8、eVex(G,p); cout<<"接受点:" p=v1; cin>>p; j=LocateVex(G,p); cout<<"权重:" 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<<"顶点数是:"<<G.vexnum<<endl; cout<<"弧数是:"<<G.arcnum<<endl; cout<<"各顶点分别是:" 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; /广度优先bool visited100;/随便设置一百个布尔值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<<"队头等于队尾!"<<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<<"访问了第"<<v<<"个顶

13、点"<<endl; cout<<"即"<<G.vexsv<<"顶点"<<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;/出队元素 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); /广度优先void main() MGraph G; CreateNet(G); /这时上面已经求出G.vexn