图的遍历——广度优先搜索
2023-09-14 09:06:55 时间
文章目录
图的遍历——广度优先搜索
广度优先搜索遍历类似于树的按层次遍历的过程。其过程为:假设从图中的某顶点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
【
相关文章
- 求二叉搜索树的下一个节点(中序遍历的下一个节点)
- 二叉搜索树的遍历方式
- Android UI(五)云通讯录项目之联系人列表,带侧滑选择,带搜索框
- Java实现 LeetCode 745 前缀和后缀搜索(使用Hash代替字典树)
- Java实现 LeetCode 700 二叉搜索树中的搜索(遍历树)
- Java实现 LeetCode 700 二叉搜索树中的搜索(遍历树)
- Java实现 LeetCode 538 把二叉搜索树转换为累加树(遍历树)
- 搜索附近人和商铺功能
- 搜索注册表内容
- (剑指Offer)面试题24:二叉搜索树的后序遍历序列
- 深入理解空间搜索算法 ——数百万数据中的瞬时搜索
- SAP WebClient UI源代码搜索工具
- SAP 电商云 Spartacus UI Quick order 产品搜索结果页面的显示逻辑
- SAP CRM的WITH_INDOBJECTS搜索参数问题
- atitit.无线网卡 不能搜索到WiFi 无线路由信号的解决不能上网
- Fiori UI上my contact加了Dr. 后搜索不出数据的奇怪问题
- 【优化算法】回溯搜索优化算法及其应用(BSA)(Matlab代码实现)
- [LeetCode] 538. 把二叉搜索树转换为累加树 ☆(中序遍历变形)
- [LeetCode] 96. Unique Binary Search Trees(给定一个数字n,有多少个唯一二叉搜索树) ☆☆☆
- CoreJava_线程并发(堵塞队列):在某个目录下搜索含有某keyword的文件
- 012-elasticsearch5.4.3【五】-搜索API【一】搜索匹配所有matchAllQuery、全文查询[matchQuery、multiMatchQuery、commonTermsQuery、queryStringQuery、simpleQueryStringQuery]