第3关：图的广度遍历

500

任务要求
参考答案
评论2

任务描述
相关知识
编程要求
测试说明

任务描述

本关任务：以邻接表存储图，要求编写程序实现图的广度优先遍历。

编程要求

根据提示，在右侧编辑器补充代码，实现以邻接表作为存储结构的图广度优先遍历算法:

void BFSTraverse(ALGraph G); //按广度优先非递归遍历图G

测试说明

平台会对你编写的代码进行测试：

测试输入： 0 lt2.txt

输入说明：第一行输入0，表示输入图的类型为有向图。第二行输入文件名，该文件里保存了图的数据信息，内容如下：

第1行为图的顶点的个数n；第2行为图的边的条数m；第3行至第n+2行是n个顶点的数据；第n+3行至第n+m+2行是m条边的数据；

预期输出： 有向图 7个顶点： 高等数学程序设计基础 C语言离散数学数据结构编译原理操作系统 9条弧(边): 高等数学→离散数学高等数学→C语言 程序设计基础→C语言程序设计基础→数据结构 C语言→数据结构 离散数学→编译原理离散数学→数据结构 数据结构→操作系统数据结构→编译原理

广度优先遍历序列： 高等数学离散数学 C语言编译原理数据结构操作系统程序设计基础

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h>
#include<limits.h> 

#include"ALGraph.h"
#include"sqqueue.h" 


void BFSTraverse(ALGraph G);  //按广度优先非递归遍历图G
int  visited[MAX_VERTEX_NUM];    // 访问标志数组(全局量)

int main()
{
	ALGraph g;
	CreateGraphF (g); // 利用数据文件创建图
	Display(g);       // 输出图
	printf("广度优先遍历序列：\n");   
	BFSTraverse(g);
	return 0;
}


void BFSTraverse(ALGraph G)
{	//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。
	/********** Begin **********/  
	int v,u,w;
	ArcNode *p;
	SqQueue Q;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	InitQueue(Q);
	for(v=0;v<G.vexnum;v++)
		if(!visited[v]){
			visited[v]=1;
			visit(G.vertices[v].data);
			EnQueue(Q,v);
			while(!QueueEmpty(Q)){
				DeQueue(Q,u);
				p=G.vertices[u].firstarc;	
				while(p){
					w=p->data.adjvex;
					if(!visited[w]){
						visited[w]=1;
						visit(G.vertices[w].data);
						EnQueue(Q,w);
					}
					p=p->nextarc;
				}
			}
		}
    printf("\n");
	/********** End **********/
}