图的广度优先遍历算法运用队列主针对邻接表有向图
源代码如下:#includeusing namespace std;#define MAX_VERTEX_NUM 20typedef int EdgeData;typedef char VertexData; //顶点数据域typedef struct node {//边表节点EdgeData cost; //边上d权值int adjvex;
·
源代码如下:
</pre><pre name="code" class="objc">#include<iostream>
using namespace std;
#define MAX_VERTEX_NUM 20
typedef 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");
}
</pre><pre name="code" class="objc">
程序运行结果图:
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献2条内容
所有评论(0)