Question

已知有N个结点的无向图，采用邻接表结构存储，要求编写算法实现广度优先搜索策略遍历图中所有顶点。

用C实现

Answer 1

//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited.仅适用于邻接表结构
void BFSTraverse1(ALGraph G,void(* Visit)(char *))
{
int v,u;
ArcNode * p;//p指向表结点
LinkQueue Q;//链队列类型
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE;//置初值为未被访问
}
InitQueue(&Q);//初始化辅助队列Q
for (v=0; v<G.vexnum; ++v)//如果是连通图，只v=0就遍历全图
{
if (! visited[v])//v尚未被访问
{
visited[v] = TRUE;//设v为已被访问
Visit(G.vertices[v].data);//访问v
EnQueue(&Q,v);//v入队
while (! QueueEmpty(Q))//队列不空
{
DeQueue(&Q,&u);//队头元素出队并置为u
for (p=G.vertices[u].firstarc; p; p=p->next)//p依次指向u的邻接顶点
{
if (! visited[p->data.adjvex])//u的邻接顶点尚未被访问
{
visited[p->data.adjvex] = TRUE;//该邻接顶点设为已被访问
Visit(G.vertices[p->data.adjvex].data);//访问该邻接顶点
EnQueue(&Q,p->data.adjvex);//入队该邻接顶点序号
}
}
}//while
}//if
}//for(v=......)
printf("\n");
}