源代码如下：#include<iostream>using namespace std;#define MAX_VERTEX_NUM 20typedef int EdgeData; typedef char VertexData; //顶点数据域 typedef struct node { // 边表节点EdgeData cost; //边上d权值int adjvex; //邻接点域struct node *next; //下一边链接指针 }EdgeNode; typedef struct { // 顶点表VertexData vertex; //顶点数据域EdgeNode *firstEdge; // 边链表头指针}VertexNode; typedef struct { // 图的邻接表VertexNode verlist[MAX_VERTEX_NUM] ;int vexnum,edgenum; //顶点数和边数}AdjGraph; //———以上是图的邻接表数据结构————————//typedef struct QUEUEnode* link;struct QUEUEnode{int item ;link next;};static link head , tail;link NEW(int item, link next){link x = new QUEUEnode ;x->item = item;x->next = next;return x;}void QUEUEinit(int maxN){head = NULL;}int QUEUEempty(){return head == NULL;} void QUEUEput(int item){if(head == NULL){head =(tail = NEW(item,head)) ;return;}tail->next = NEW(item,tail->next);tail = tail->next;}int QUEUEget(){int item = head->item;link t = head->next;delete head;head = t;return item;} //————–以上的队列的数据结构———————–//void printAdjGraph(AdjGraph G){cout<<"得到的有向图如下："<<endl;int i ;for(i = 0;i<G.vexnum;i++){cout<<G.verlist[i].vertex<<"–>";EdgeNode *e = G.verlist[i].firstEdge;while(e!=NULL){cout<<e->adjvex<<"–>";e = e->next; }cout<<endl;} }//建立图的邻接表 AdjGraph createAdjGraph(AdjGraph G){ int i,j,k,w;cout<<"输入顶点数和边数"<<endl;cin>>G.vexnum>>G.edgenum;cout<<"输入顶点信息"<<endl;for(i = 0 ; i<G.vexnum;i++){cin>>G.verlist[i].vertex;G.verlist[i].firstEdge = NULL; //将边表置为空表 }EdgeData weight;int head;int tail;cout<<"输入第tail号边表的前端索引head,和权值weight，，如(tail head weight)"<<endl; for(k=0;k<G.edgenum;k++){ cin>>tail>>head>>weight; EdgeNode *p = new EdgeNode; p->adjvex = head;p->cost = weight;p->next = G.verlist[tail].firstEdge;G.verlist[tail].firstEdge = p; // 一条边是 tail—->head//创建无向图的话就再加上下面的代码 //p = new EdgeNode;// p->adjvex = tail;//p->cost = weight;//p->next = G.verlist[head].firstEdge;//G.verlist[head].firstEdge = p;if(k==G.edgenum-1)printAdjGraph(G); } return G; }bool visited[MAX_VERTEX_NUM] ; int dfn[MAX_VERTEX_NUM]; //顶点的先深编号 int count = 1;void BFS1(AdjGraph G,int K){int i; EdgeNode *p;QUEUEinit(40);cout<<G.verlist[K].vertex<<endl;visited[K] = true;QUEUEput(K);while(!QUEUEempty()){i = QUEUEget();p = G.verlist[i].firstEdge;while(p){if(!visited[p->adjvex]){cout<<G.verlist[p->adjvex].vertex<<endl;visited[p->adjvex] = true;QUEUEput(p->adjvex);}p = p->next;}}//若是邻接矩阵则用下面的程序替代while(p)程序段 //int j;//while(!QUEUEempty()){//i = QUEUEget();//for(j=0;j<G.vexnum;j++)//if(G.edge[i][j]==1 && !visited[j]){//cout<<G.verlist[j]<<endl;//visited[j] = true;//QUEUEput(j);//}//}//———以下是图的邻接矩阵数据结构————-////#define MAX_VERTEX_NUM 20//typedef int QElemType; //typedef int EdgeData;//typedef char VertexData;//typedef struct //{// VertexData verlist[MAX_VERTEX_NUM];//顶点表//EdgeData edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵–可试为边之间的关系 //int vexnum,edgenum;//顶点数和边数//}MTGraph;} //广度优先遍历主程序 void BFSTraverse(AdjGraph G){int i ; for(i=0;i<G.vexnum;i++) visited[i]=false;for(i=0;i<G.vexnum;i++)if(!visited[i])BFS1(G,i);} main(){AdjGraph G ;G = createAdjGraph(G);cout<<"广度优先遍历的结果："<<endl;BFSTraverse(G);system("pause");}程序运行结果图<img src="?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />
版权声明：本文为博主原创文章，未经博主允许不得转载。
因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。
