【优秀题解】问题 1703: 图的遍历——广度优先搜索
【优秀题解】问题 1703: 图的遍历——广度优先搜索
解题思路:
1):为了这里代码把输入的邻接矩阵转化为了邻接表，之后再进行BFS。
2):广度优先遍历相当于树的层次遍历：选取图中任意一个顶点开始遍历，然遍历该节点的所有未被访问的边表节点，再把访问了的边表节点入队列，出队列一个节点，循环上述过程，直到队列为空。
①：选取图中任意顶点v开始遍历（题目选取为编号为0）
②：先访问v顶点，让后再把v入队列
③：若队列不为空循环下面部分
1）：出队列一个节点
2）：让p指向他的第一个边表节点
3）：若p不为空，循环遍历v的所有没有被访问的边表节点，访问后把被访问节点入队列 ④：队列空结束遍历
邻接矩阵转化为邻接表实现代码：
void creat_adjlist(agraph G,int n)
{
G->n=n;/*保存顶点数*/
/*建立邻接表的顶点表*/
G->adjlist=(vnode)malloc(n*sizeof(VNode));
/*下面分别建立边表节点*/
int b;/*保存邻接矩阵中的0，1*/
ArcNode Head;/*为边表节点建立头节点*/
Head.nextarc=NULL;
arcnode p=&Head;/*让p指向头节点*/
arcnode q;
/*创建邻接表*/
for(int i=0;i<n;i++)
{ /*一定要单独建立每一个顶点的边表*/
/*每次建立完一个边表后，初始化*/
Head.nextarc=NULL;
p=&Head;
for(int j=0;j<n;j++)
{
scanf("%d",&b);
if(b==1)/*顶点i到顶点j之间有边，则建立边表节点j*/
{ /*创建边表节点*/
q=(arcnode)malloc(sizeof(ArcNode));
q->adjvex=j;/*保存该边表节点编号*/
/*后插入节点*/
p->nextarc=q;
q->nextarc=NULL;
p=q;
}
}
/*最后把该边表加入邻接表中对应顶点节点后*/
G->adjlist[i].firstarc=Head.nextarc;
}
}
注意：每个顶点的边表单独建立，也就是每次建立时要初始化，否则不正确；
参考代码:
#include<stdio.h>
#include<malloc.h>
typedef struct ArcNode_{
int adjvex;
struct ArcNode_ *nextarc;
}*arcnode,ArcNode;
typedef struct VNode_{
char data;
ArcNode * firstarc;
}*vnode,VNode;
typedef struct Agraph_{
VNode *adjlist;
int n,e;
}*agraph,Agraph;
void BFS_(Agraph *G,int v,int *visit);
void creat_adjlist(agraph G,int n);
/*=================================================*/
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
Agraph G;
creat_adjlist(&G,n);
int visit[n];/*定义访问数组*/
for(int i=0;i<n;i++)
visit[i]=0;
BFS_(&G,0,visit);
printf("\n");/*行尾换行*/
}
return 0;
}
/*===============================================*/
void creat_adjlist(agraph G,int n)
{
G->n=n;/*保存顶点数*/
/*建立邻接表的顶点表*/
G->adjlist=(vnode)malloc(n*sizeof(VNode));
/*下面分别建立边表节点*/
int b;/*保存邻接矩阵中的0，1*/
ArcNode Head;/*为边表节点建立头节点*/
Head.nextarc=NULL;
arcnode p=&Head;/*让p指向头节点*/
arcnode q;
/*创建邻接表*/
for(int i=0;i<n;i++)
{ /*一定要单独建立每一个顶点的边表*/
/*每次建立完一个边表后，初始化*/
Head.nextarc=NULL;
p=&Head;
for(int j=0;j<n;j++)
{
scanf("%d",&b);
if(b==1)/*顶点i到顶点j之间有边，则建立边表节点j*/
{ /*创建边表节点*/
q=(arcnode)malloc(sizeof(ArcNode));
q->adjvex=j;/*保存该边表节点编号*/
/*后插入节点*/
p->nextarc=q;
q->nextarc=NULL;
p=q;
}
}
/*最后把该边表加入邻接表中对应顶点节点后*/
G->adjlist[i].firstarc=Head.nextarc;
}
}
/*===============================================*/
void BFS_(Agraph *G,int v,int *visit)
{
int que[G->n];/*建立队列*/
int front=0,rear=0;
/*输出当前遍历到的节点编号*/
printf("%d ",v);
visit[v]=1;/*编号为v的节点设置为已访问*/
/*把该节点入队列*/
rear=(rear+1)%G->n;
que[rear]=v;
int J;
ArcNode *p;/*定义一个边表节点指针，下面遍历边表节点使用*/
while(front!=rear)
{
/*队列节点出队列*/
front=(front+1)%G->n;
J=que[front];
p=G->adjlist[J].firstarc;
/*开始遍历边表节点*/
while(p!=NULL)
{
if(visit[p->adjvex]==0)/*如果该p->adjvex编号所指节点没有被访问*/
{
/*访问且输出该节点编号*/
printf("%d ",p->adjvex);
visit[p->adjvex]=1;
/*把该节点入队列*/
rear=(rear+1)%G->n;
que[rear]=p->adjvex;
}
p=p->nextarc;/*p指向下一个边表节点*/
}
}
}
（本文为我站大神“ Manchester”创作）