图的广度优先搜索(BFS)——C语言版
图的广度搜索类似于树的按层次遍历,用的是队列来解决。
BFS的大概过程为:假设从顶点1出发进行BFS,首先访问到与1有关系的两个顶点2、3 、4
再通过寻找与2,3,4两点有关的顶点......以此类推。可以把BFS的过程比作队列先进先出,从顶点1开始时,先对1入队列,找到与1有关系的点后,将两顶点入队列,再将1出队列,进而对每一个顶点进行访问。输出结果为:1、2、3、4、6、5
代码如下:
/**广度搜寻**/
void ArrayGraph_BFS(ArrayGraph *G,int n,int a)///G为已知图,n为开始访问的位置,a为图的顶点个数
{
int visited[MAXN];///visited数组用于标记顶点是否被访问
int i;///循环变量
for(i=0;i<a;i++)///对visited数组进行初始化,0为未访问,1为以访问,避免在搜寻过程中碰见闭环
{
visited[i]=0;
}
int flag=0;///flag为标记变量,用于防止出现两个或以上的连通分量导致的图为搜寻完成。
queue <int> Queue;///使用队列来实现BFS
int tou;///代表队首位置元素
while(!flag)
{
printf(" %c \t",G->vertex[n]);
visited[n]=1;///将起始位置标记为已访问
Queue.push(n);///起始顶点入队列
while(!Queue.empty())///当队列不为空时,循环操作
{
tou=Queue.front();///取队首位置元素
Queue.pop();///将队首出队列
for(i=0;i<a;i++)
{
if(G->arcs[tou][i]!=0&&visited[i]==0)///当第i个顶点与G->vertex[tou]有关系,且未被访问时
{
printf(" %c \t",G->vertex[i]);
visited[i]=1;///标记访问
Queue.push(i);///入队列
}
}
}
flag=1;///将flag标记为1,当顶点全部访问完成则结束循环,否则循环继续
for(i=0;i<a;i++)
{
if(visited[i]==0)///此循环用于判断顶点是否访问完成
{
flag=0;
n=i;
break;
}
}
}
}