Problem 2082 --算法7-6:图的遍历——广度优先搜索

2082: 算法7-6:图的遍历——广度优先搜索

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $23$ 正确数量 $157$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 搜索 STL
广度优先搜索遍历类似于树的按层次遍历的过程。其过程为:假设从图中的某顶点v出发,在访问了v之后依次访问v的各个未曾被访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点。重复上述过程,直至图中所有顶点都被访问到为止。
其算法可以描述如下:
在本题中,读入一个无向图的邻接矩阵(即数组表示),建立无向图并按照以上描述中的算法遍历所有顶点,输出遍历顶点的顺序。

输入的第一行包含一个正整数n,表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1,对于第i行的第j个0或1,1表示第i个顶点和第j个顶点有直接连接,0表示没有直接连接。当i和j相等的时候,保证对应的整数为0。
输入保证邻接矩阵为对称矩阵,即输入的图一定是无向图。
只有一行,包含n个整数,表示按照题目描述中的广度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格,并请注意行尾输出换行。
4
0 0 0 1
0 0 1 1
0 1 0 1
1 1 1 0
0 3 1 2 
在本题中,需要熟练掌握图的邻接矩阵存储方式。在建立完成无向图之后,需要严格按照题目描述的遍历顺序对图进行遍历。另外,算法中描述的FirstAdjVex函数和NextAdjVex函数,需要认真的自行探索并完成。在本题中需要使用队列结构,需要对队列的概念进行复习。
通过这道题目,应该能够对图的广度优先搜索建立更加直观和清晰的概念。

推荐代码 查看2082 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 却又像风捉摸不住 425705 2019-05-12 22:52:53
内存最少[$948 $KB] 范晋豪@信息与计算科学142 152725 2017-11-16 15:10:16
第一AC 范晋豪@信息与计算科学142 152724 2017-11-16 15:10:16
第一挑战 范晋豪@信息与计算科学142 152724 2017-11-16 15:10:16

赛题来源/所属竞赛 数据结构高分笔记 数据结构高分笔记

竞赛编号 竞赛名称 竞赛时间 访问比赛
1771 2023-2024-1学期<编译原理> 第15-17周练习:图算法、中间代码生成优化实验【21计算机1234】 2023-12-11 09:00:00 请登录