数据结构-邻接表广度优先搜索(C语言版)

对于一个有向图无向图，我们下面介绍第二种遍历方式。

广度优先搜索，即优先对同一层的顶点进行遍历。

如下图所示：

该例子，我们有六个顶点， 十条边。

对于广度优先搜索，我们先搜索a，再搜索abcd，最后搜索ef。

而对于广度优先搜索，我们需要一个队列来辅助我们进行广度优先搜索（先进先出）。

同时我们还需要一个visit数组来判断某个顶点是否已经被搜索过了。

#include<stdio.h>#define MAX_NUM 100
typedef struct ArcNode{				//边 int adjvex;struct ArcNode *next;int weight;
}ArcNode;		typedef struct{						//头结点 char vertex;ArcNode *firstarc;
}VNode;typedef VNode Adjlist[MAX_NUM];			//邻接表 typedef struct{			//建立邻接表 Adjlist adjlist;int vexnum,arcnum;
}ALGraph;void DFSTraverse(ALGraph *G)		//深度优先搜索 
{int v;int visit[G->vexnum];for(v=0;v<G->vexnum;v++){visit[v] = 0;}for(v=0;v<G->vexnum;v++){if(visit[v]==0)DFS(G,v,visit);}
}void DFS(ALGraph *G,int v,int *visit)		//深度优先搜索后继结点判断 
{int w;ArcNode *p;printf("访问顶点:%c\n",G->adjlist[v].vertex);visit[v] = 1;p = G->adjlist[v].firstarc;while(p){w = p->adjvex;if(visit[w]==0)DFS(G,w,visit);p = p->next;}
}void BFSTraverse(ALGraph *G)		//广度优先搜索后继节点判断 
{int v,w,u;int Q[G->vexnum+1],r,f;int visit[G->vexnum];for(v=0;v<G->vexnum;v++)visit[v] = 0;f = 0,r = 0;for(v=0;v<G->vexnum;v++){if(visit[v]==0){visit[v] = 1;printf("第%d个结点是->%c\n",v,G->adjlist[v].vertex);Q[r] = v;r = (r+1)%(G->vexnum+1);while(f!=r){u = Q[f];f = (f+1)%(G->vexnum+1);ArcNode *p = G->adjlist[u].firstarc;while(p){if(visit[p->adjvex]==0){visit[p->adjvex] = 1;printf("第%d个结点是->%c\n",p->adjvex,G->adjlist[p->adjvex].vertex);Q[r] = p->adjvex;r = (r+1)%(G->vexnum+1);}p = p->next;}}}}
}int main()
{return 0;
}

运行结果如下：