无向图采用邻接表存储结构,编写算法输出图中各连通分量的节点序列
发布网友
发布时间：2022-03-27 09:48
共1个回答
热心网友
时间：2022-03-27 11:17
//按广度优先非递归遍历图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");
}追问可以给出完整的代码吗，谢谢
