无向图广度优先遍历c语言实现

这里记录一下无向图的广度优先遍历&＃xff0c;无向图用邻接表表示&＃xff0c;使用的图的示例图如下&＃xff0c;关于图的表示可以参照博客&＃xff1a;无向图的表示&＃xff1a;邻接矩阵和邻接表&＃xff0c;这里不再赘述&＃xff0c;无向图的表示的代码被封装到头文件queue.h 中。
另外还涉及到C语言的队列问题&＃xff0c;可以参照博客&＃xff1a;C 循环队列实现&＃xff0c;同样不再赘述&＃xff0c;循环队列实现的代码被封装到头文件graph_represent.h 中。

程序使用示例图&＃xff1a;

实现要点&＃xff1a;
每个定点有三个状态&＃xff0c;-1,0,1&＃xff0c;-1&＃xff1a;表示未发现的节点&＃xff1b;0&＃xff1a;表示已经发现但是还没有处理的节点&＃xff1b;1&＃xff1a;表示已经处理的节点。在遍历过程中同样保存了“树边&＃xff08;tree edge&＃xff09;”,树边表示在遍历过程中经历过的点。
程序框架如下&＃xff1a;

代码如下&＃xff1a;

#include
#include
#include "queue.h"
#include "graph_represent.h"void BFS(struct vNode** adj,int n,int s,int* parent){int* color &＃61; (int*)malloc(sizeof(int)*(n)); //-1:未发现&＃xff0c;0:已发现&＃xff0c;未处理, 1:已经处理int i;Queue* pending &＃61; createQue(n); //创建队列for(i&＃61;0;i1; //所有节点处于“未发现”状态}parent[s] &＃61; -1;color[s] &＃61; 0;add(pending,s); //入队操作while(!isEmpty(pending)){int v &＃61; poll(pending);struct vNode* w &＃61; adj[v];while(w !&＃61; NULL){if(color[w->value]&＃61;&＃61;-1){color[w->value] &＃61; 0;add(pending,w->value);parent[w->value] &＃61; v;/**在这里处理树边**/}w &＃61; w->next;}printf("%d ",v);/**在这里处理节点**/color[v] &＃61; 1;}printf("\n");
}void main(){//获得默认图,一共有7个节点int n &＃61; 7;struct vNode** adjVertics &＃61; default_wraper();int* parent &＃61; (int*)malloc(sizeof(int)*n);printf("\nbreadth first search:\n");BFS(adjVertics,n,2,parent);//从第二个节点开始遍历
}

从第二个节点开始遍历&＃xff0c;输出为&＃xff1a;2 0 1 3 5 4 6