这里记录一下无向图的广度优先遍历,无向图用邻接表表示,使用的图的示例图如下,关于图的表示可以参照博客:无向图的表示:邻接矩阵和邻接表,这里不再赘述,无向图的表示的代码被封装到头文件queue.h
中。
另外还涉及到C语言的队列问题,可以参照博客:C 循环队列实现,同样不再赘述,循环队列实现的代码被封装到头文件graph_represent.h
中。
程序使用示例图:
实现要点:
每个定点有三个状态,-1,0,1,-1:表示未发现的节点;0:表示已经发现但是还没有处理的节点;1:表示已经处理的节点。在遍历过程中同样保存了“树边(tree edge)”,树边表示在遍历过程中经历过的点。
程序框架如下:
代码如下:
#include
#include #include "queue.h"#include "graph_represent.h"void BFS(struct vNode** adj,int n,int s,int* parent){
int* color = (int*)malloc(sizeof(int)*(n));
//-1:未发现,0:已发现,未处理, 1:已经处理 int i;
Queue* pending = createQue(n);
//创建队列 for(i=0;
ii++){ i++){
int="" struct="" v="poll(pending);
" w="" w-="">value]==-1){
color[w->value] = 0;
add(pending,w->value);
parent[w->value] = v;
/**在这里处理树边**/ }
w = w->next;
}
printf("%d ",v);
/**在这里处理节点**/ color[v] = 1;
}
printf("n");
}
void main(){
//获得默认图,一共有7个节点 int n = 7;
struct vNode** adjVertics = default_wraper();
int* parent = (int*)malloc(sizeof(int)*n);
printf("nbreadth first search:n");
BFS(adjVertics,n,2,parent);
//从第二个节点开始遍历}
>
从第二个节点开始遍历,输出为:2 0 1 3 5 4 6