[C] 图的广度优先遍历

news/2024/2/29 2:01:11

图的广度优先遍历

我一直觉得图的遍历没有地图类型的题目难,遍历嘛,每个点都走一遍就行了。

但是给定地图求面积啊,数量啊的那种题目,花样挺多的。

图的遍历真挺难把人绕晕的,关于广度优先,理解好层层递进这个概念就好。

在这里插入图片描述

  • 还是这张图,上次我用了深度优先方法去遍历它:图的深度优先遍历
  • 这次用广度优先(BFS)法去遍历它

代码实现

#include<stdio.h>int book[2000], a[2000][2000], que[2000];
int sum, n, m;
int head, tail;int main()
{int i, j, m, x, y;int cur;scanf("%d %d", &n, &m);for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)if (i == j)a[i][j] = 0;elsea[i][j] = 99999999;for (i = 1; i <= m; i++){scanf("%d %d", &x, &y);a[x][y] = 1;a[y][x] = 1;}head = 1;tail = 1;que[tail] = 1;book[1] = 1;tail++;while (head < tail){//当前正在访问的顶点的编号cur = que[head];// 从1~n进行尝试for (i = 1; i <= n; i++){if (a[cur][i] == 1 && book[i] == 0){que[tail] = i;tail++;book[i] = 1;}//如果tail>n则表示所有顶点都被访问过if (tail > n){break;}}//这里不要忘记,拓展完之后,要将头指针+1head++;}for (i = 1; i < tail; i++){printf("%d ", que[i]);}return 0;
}

遍历结果为
在这里插入图片描述


http://www.ppmy.cn/news/607568.html

相关文章

数据湖(十四):Spark与Iceberg整合查询操作

文章目录 Spark与Iceberg整合查询操作 一、DataFrame API加载Iceberg中的数据 二、查询表快照

SpringBoot项目中功能集成的方式

原文合集地址如下&#xff0c;有需要的朋友可以关注 本文地址 合集地址 SpringBoot项目中功能集成的方式 接口集成 基于HTTP协议的集成方式 协议和通信 HTTP是一种基于客户端-服务器模型的协议。确定使用的HTTP版本&#xff08;如HTTP/1.1或HTTP/2&#xff09;以及通信过…

计算机考试机试题目word文档,计算机考试 word

2006年教师职称计算机考试试题(第5章)第五章Word 2000文字处理软件1、打开WORD文档一般是指(B)A把文档的内容从内存中读入并在屏幕上显示出来B把文档的内容从磁盘上调入内存并在屏幕上显示出来C为指定的文档开设一个新的空白文档窗口  D显示并打印指定的文档内容2、关于WORD的…

TVM darknet yolov3算子优化与量化代码的配置方法

TVM darknet yolov3算子优化与量化代码的配置方法 使用以下接口函数  tvm.relay.optimize  quantize.quantize 实际代码&#xff1a; convert nnvm to relay print(“convert nnvm symbols into relay function…”) #from nnvm.to_relay import to_relay func, params …

[JavaScript] JavaScript 数组挖掘,不只是讲数组哟

课程来源&#xff1a;后盾人 数组引用类型分析 数组的定义 const array new Array(hello, dust, 1, 2, 3, 4, 5) console.log(array) let arr [hello, dust, 1, 2, 3, 4, 5] console.log(arr)运行结果: 数组是引用类型的 体现: let arr [hello, dust, 1, 2, 3, 4, 5] c…

机器学习——标准化/归一化的目的、作用和场景

对每个特征进行归一化处理&#xff0c;使得每个特征的取值缩放到0~1之间。这样做有两个好处&#xff1a; 模型训练更高效。特征前的权重大小可代表该变量对预测结果的贡献度&#xff08;因为每个特征值本身的范围相同&#xff09;。&#xff08;一&#xff09;归一化的作用 在机…

华东理工大学计算机应用基础,最新华东理工大学计算机应用基础网上作业及全部答案...

精品文档华东理工大学计算机应用基础网上作业及全部答案2012计算机应用基础答案:一、选择题1、文件夹是用来对应用程序、文件进行分组的&#xff0c;以下说法中()正确。答&#xff1a;一个文件夹内可以包含文件、应用程序和下一级子文件夹3、计算机的内存以字节(byte)为存储单元…

3D卷积,代码实现

3D卷积&#xff0c;代码实现 三维卷积&#xff1a;理解用例-发现 在图像卷积神经网络内核中&#xff0c;包含3D卷积及其在3D MNIST数据集上的实现。 什么是卷积&#xff1f; 从数学上讲&#xff0c;卷积是一种积分函数&#xff0c;表示一个函数g在另一个函数f上移动时的重叠量…

[C] 图的广度优先搜索——最少转机

我一直认为用C语言来描述数据结构&#xff08;尤其是这种简单的&#xff09;是一个非常不错的方式。 C语言在表示数据&#xff0c;存取数据&#xff0c;表现数据结构里都没有那么多“捷径”可以走&#xff0c;所以用C语言写基础的数据结构的代码&#xff0c;是非常方便读者理解…

定时开关手电筒

定时开关手电筒 前言 最近为了节省开支&#xff0c;决定少开出租屋里的大灯&#xff0c;屋里又不能全是黑暗&#xff0c;怪吓人的&#xff0c;而且另买台灯也是笔不小的支出。 于是想到使用手机的手电筒做为一个照明工具&#xff0c;如果把照明手机固定到桌子上的话&#xf…

大数据必学Java基础(二十二):循环结构

文章目录 循环结构 一、while 1、语法结构 2、练习:1+2+3+4+5 3、总结

https://blog.csdn.net/blmoistawinde/article/details/84329103

背景 很多场景需要考虑数据分布的相似度/距离&#xff1a;比如确定一个正态分布是否能够很好的描述一个群体的身高&#xff08;正态分布生成的样本分布应当与实际的抽样分布接近&#xff09;&#xff0c;或者一个分类算法是否能够很好地区分样本的特征&#xff08;在两个分…

Centos7完整安装

一、前言 由于使用VMware workstation使用典型安装以及默认安装方式进行安装的Centos多存在组件不足的问题&#xff0c;这使得使用上述方式进行安装的系统在一些特定情况下需要安装组件&#xff0c;致使系统不是很便利&#xff0c;本文提供了在VMware workstation下进行完整安装…

[C] [最短路] 只有5行的算法:Floyd-Warshall

终于学到求最短路了&#xff0c;终于来到我最喜欢的算法——Floyd-Warshall了&#xff01;今天还有点小激动呢&#xff01; 我喜欢它&#xff0c;当然是因为它逻辑十分简单咯&#xff01;真的只有5行诶&#xff01; Floyd-Warshall算法 题目描述 暑假&#xff0c;小哼准备去一…

LLVM Backend技术

LLVM Backend技术 LLVM编译器介绍 LLVM 是一个编译器基础设施的设计与实现&#xff0c;具有独特的多阶段优化系统。广泛支持过程间和配置文件驱动的优化&#xff0c;同时对于商业编译器系统也十分高效。 LLVM 虚拟指令集把系统作为一个整体关联到一起&#xff0c;使用高级的类型…

云原生(三十二) | Kubernetes篇之平台存储系统介绍

文章目录 Kubernetes平台存储系统介绍 一、Ceph 1、基本概念 二、Rook 1、基本概念

python Matplotlib 系列教程(三)——绘制直方图和条形图

202140420 ################################### 20210713 以这个为主 import matplotlib.pyplot as plt# matplotlib.axes.Axes.hist() 方法的接口 n, bins, patches plt.hist(xd, binsauto, color#0504aa,alpha0.7, rwidth0.85) plt.grid(axisy, alpha0.75) plt.xlabel(Va…

Qt安卓AMD64-v8a配置OpenCV4.5.2

1.OpenCV官方网下载OpenCV的安卓平台SDK并解压 在工程的配置pro文件中添加opencv包含路径INCLUDEPATH与库LIBS unix {ANDROID_OPENCV = C:\Users\dev2\Desktop\OpenCV-android-sdk\sdk\nativeINCLUDEPATH += $$ANDROID_OPENCV/jni/include/opencv2 \$$ANDROID_OPENCV/jni/in…

量子力学在计算机上的应用,量子力学在医学科学中的应用

量子力学在医学科学中的应用退休教师 王京贵医学&#xff0c;是通过科学或技术的手段处理人体的各种疾病、病变或正常发育。它是生物学的应用学科&#xff0c;分基础医学、临床医学。它是一个从预防到治疗疾病的系统学科&#xff0c;研究领域大方向包括基础医学、临床医学、法…

[C] Dijkstra算法——通过边实现松弛

Dijkstra算法——通过边实现松弛 本算法学习指定一个点&#xff08;源点&#xff09;到其余各个顶点的最短路径&#xff0c;也叫做单源最短路径例如求下图1号顶点到2&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;6号顶点的最短路径这个时候你可能就要问了&#xff0c;…
最新文章