网站可以增加关键词吗,网站开发哪家公司,网站成功上线报道,都兰县建设局交通局网站500
任务要求参考答案评论2
任务描述相关知识编程要求测试说明 任务描述
本关任务#xff1a;以邻接表存储图#xff0c;要求编写程序实现图的广度优先遍历。
相关知识
广度优先遍历类似于树的按层次遍历的过程。
假设从图中某顶点v出发#xff0c;在访问了v之后依次访…
500
任务要求参考答案评论2
任务描述相关知识编程要求测试说明 任务描述
本关任务以邻接表存储图要求编写程序实现图的广度优先遍历。
相关知识
广度优先遍历类似于树的按层次遍历的过程。
假设从图中某顶点v出发在访问了v之后依次访问v的各个未曾访问过和邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问直至图中所有已被访问的顶点的邻接点都被访问到。
若此时图中尚有顶点未被访问则另选图中一个未曾被访问的顶点作起始点重复上述过程直至图中所有顶点都被访问到为止。
换句话说广度优先遍历图的过程中以v为起始点由近至远依次访问和v有路径相通且路径长度为1,2,…的顶点。
本关卡提供顺序队列sqqueue的相关操作和功能顺序队列数据类型定义及相关操作函数接口定义如下在进行图的广度优先遍历的过程中可以根据需要调用以下操作 struct SqQueue{QElemType *base; // 初始化的动态分配存储空间int front; // 头指针若队列不空指向队列头元素int rear; // 尾指针若队列不空指向队列尾元素的下一个位置};void InitQueue(SqQueue Q); // 构造一个空循环队列Q void DestroyQueue(SqQueue Q); // 销毁循环队列QQ不再存在void ClearQueue(SqQueue Q); // 将Q清为空循环队列int QueueEmpty(SqQueue Q); // 若循环队列Q为空队列则返回TRUE否则返回FALSEint QueueLength(SqQueue Q); // 返回Q的元素个数即循环队列的长度int GetHead(SqQueue Q,QElemType e); // 若循环队列不空则用e返回Q的队头元素并返回OK否则返回ERRORint EnQueue(SqQueue Q,QElemType e); // 插入元素e为循环队列Q的新的队尾元素int DeQueue(SqQueue Q,QElemType e); // 若循环队列不空则删除Q的队头元素用e返回其值并返回OK否则返回ERRORvoid QueueTraverse(SqQueue Q,void(*vi)(QElemType)); // 从队头到队尾依次对队列Q中每个元素调用函数vi()
编程要求
根据提示在右侧编辑器补充代码实现以邻接表作为存储结构的图广度优先遍历算法:
void BFSTraverse(ALGraph G); //按广度优先非递归遍历图G
测试说明
平台会对你编写的代码进行测试
测试输入 0 lt2.txt 输入说明 第一行输入0表示输入图的类型为有向图。 第二行输入文件名该文件里保存了图的数据信息内容如下 第1行为图的顶点的个数n 第2行为图的边的条数m 第3行至第n2行是n个顶点的数据 第n3行至第nm2行是m条边的数据 预期输出 有向图 7个顶点 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统 9条弧(边): 高等数学→离散数学 高等数学→C语言 程序设计基础→C语言 程序设计基础→数据结构 C语言→数据结构 离散数学→编译原理 离散数学→数据结构 数据结构→操作系统 数据结构→编译原理
广度优先遍历序列 高等数学 离散数学 C语言 编译原理 数据结构 操作系统 程序设计基础
#includestdio.h
#includestdlib.h
#includestring.h
#includelimits.h #includeALGraph.h
#includesqqueue.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(v0;vG.vexnum;v)visited[v]0;InitQueue(Q);for(v0;vG.vexnum;v)if(!visited[v]){visited[v]1;visit(G.vertices[v].data);EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);pG.vertices[u].firstarc; while(p){wp-data.adjvex;if(!visited[w]){visited[w]1;visit(G.vertices[w].data);EnQueue(Q,w);}pp-nextarc;}}}printf(\n);/********** End **********/
}输出说明 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行为从“高等数学”出发进行广度优先遍历的序列。
