程序员经验分享-hwhale

数据结构——图的广度优先遍历（BFS）

2023-11-11

　　本文内图的存储方式是邻接矩阵，不过BFS的具体实现代码与图的存储结构无关。

　　BFS的遍历方法，与树的层次遍历几乎一样。

　　在实现树的层次遍历时，需要找到结点的所有子结点

　　在实现BFS时，需要找到该结点的所有邻接点

　　所以在实现BFS之前，需要先学习   寻找第一个邻接点（FirstNeighbor）与 寻找下一个邻接点（NextNeighbor） 如何实现

　　（这里的图存储的是char类型的变量）

目录

　　　　　寻找ａ的第一个邻接点

　　　　　寻找ａ的下一个邻接点

　　　　　BFS的实现

寻找ａ的第一个邻接点

　　因为是char类型的变量，所以在刚开始需要将此变量ａ在邻接矩阵中的位置找到。找到了返回数组中的位置，找不到返回-1.

//寻找位置
int find(Adj_Matrix q, char a)
{
	for (int i = 0; i < q.NumData; i++)
		if (q.data[i] == a)
			return i;
	return -1;
}

　

　　在邻接矩阵中，寻找临界点只需遍历ａ所在的行数，判断边是否存在，存在则返回所在的位置，不存在则返回-1.　

　　从而找到第一个邻接点．

//寻找第一个临界点
int FirstNeighbor(Adj_Matrix q, char a)
{
	int m = find(q, a);
	if (m == -1)
		return -1;

	for
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法

数据结构

算法

数据结构——图的广度优先遍历（BFS） 的相关文章

随机推荐

  • 计算机视觉（四）：使用K-NN分类器对CIFAR-10进行分类

    1 引言 之前我们学习了KNN分类器的原理 现在让我们将KNN分类器应用在计算机视觉中 学习如何使用这个算法来进行图片分类 2 准备工作 创建项目结构如图所示 在datasets文件中下载数据集Cifar 10 k nearest neig

  • 基于Tensorflow搭建卷积神经网络CNN（花卉识别）保姆及级教程

    项目介绍 TensorFlow2 X 搭建卷积神经网络 CNN 实现人脸识别 可以识别自己的人脸哦 搭建的卷积神经网络是类似VGG的结构 卷积层与池化层反复堆叠 然后经过全连接层 最后用softmax映射为每个类别的概率 概率最大的即为识别

  • C#使用checked检查溢出

    在进行数值类型之间的强制转换时 可能会丢失信息 比如将 int 类型转换为 short 类型时 如果 int 类型会的值大于 short 类型所能存储的最大值 那么就会发生溢出 1 使用checked检查溢出 通常情况下 发生溢出时并不会自

  • this指向

    1 在全局环境中的this window 无论是否在严格模式下 在全局执行环境中 在任何函数体外部 this 都指向全局对象 use strict console log this window console log this windo

  • 联邦学习 深度学习对抗攻击

    联邦学习本身 联邦学习 实际上是一种加密的分布式机器学习技术 参与各方可以在不披露底层数据和底层数据的加密 混淆 形态的前提下共建模型 如果机构之间的数据无法互通 一家企业一家机构数据量有限 或者是少数巨头公司垄断大量数据 而小公司很难获得

  • 移动端Touch （触摸）事件

    一 常见的触摸事件 touchstart touchmove和touchend touchstart事件 当手指触摸屏幕时候触发 即使已经有一个手指放在屏幕上也会触发 touchmove事件 当手指在屏幕上滑动的时候连续地触发 在这个事件发

  • 怎么选择boost升压电路的电感？只要三个公式

    原文来自公众号 工程师看海 添加微信 chunhou0820 获取仿真文件 BOOST电源架构是一种非常经典的升压电源方案 它是利用开关管开通和关断的时间比率 维持稳定输出的一种开关电源 它以小型 轻量和高效率的特点被广泛应用在各行业电子设

  • 1-1、Qt基本概念以及界面绑定信号与槽的实例

    1 各种程序格式的选择方式 2 例子 新建mainwindow的项目 在ui拖动一个pushbuttton 点击界面下的信号与槽的部分 点击 然后选择发送者 信号 接收者 槽 一下为源码 sampl 1 pro Project create

  • yum提示 “Cannot retrieve metalink for repository: epel/x86_64” 的解决方法

    今天在centos7服务器上用yum的时候发现 yum命令不能用了 不管用yum什么命令都会出现如下提示 完整的错误提示如下 One of the configured repositories failed Unknown and yum

  • 深入理解［观察者模式］原理与技术

    观察者模式 Observer Pattern 也叫做发布 订阅 Publish Subscribe 模式 模型 视图 Model View 模式 这个模式的一个最重要的作用就是解耦 也就是将被观察者和观察者进行解耦 使得他们之间的依赖性更小

  • 【华为OD机试真题 C++】计算最大乘积 【2022 Q4

    前言 华为OD机试真题 C 本专栏包含华为OD机试真题C 解答 会实时更新收纳网友反馈 为大家更新最新的华为德科OD机试试题 为大家提供学习和练手的题库 订阅本专栏后可私信进交流群哦 答案仅供参考 不可照抄哦 题目描述 计算最大乘积 给定一

  • 【Unity3D】粒子光环

    作业要求 参考http i remember fr en 这类网站 使用粒子流编程控制制作一些效果 如 粒子光环 这个网站打不开 参考了一下师兄们的博客的图片 我看了一下 我感觉和上课做的粒子海洋有一些相似 就是需要变成一个环形 制作流程

  • JavaScript 数字去掉小数点后的0

    JavaScript 数字去掉小数点后的0 方法很简单 JavaScript提供了现成的方法 parseFloat function parseNum value value parseFloat value

  • 从头再来系列-Markdown基本语法

    以下内容摘抄于网络 Markdown 简介 Markdown 是一种轻量级标记语言 它允许人们使用易读易写的纯文本格式编写文档 Markdown 语言在 2004 由约翰 格鲁伯 英语 John Gruber 创建 Markdown 编写的

  • oracle基础知识

    1 oracle特点 2 oracle体系 实例 一组oracle后台进程以及在服务器中分配的共享内存区域 数据库 基于磁盘的数据文件 控制文件 日志文件 参数文件和归档文件等组成的物理文件集合 数据库服务器 三者之间的关系 实例用于控制和

  • 【DBeaver日常】查询出结果后，无法回到SQL编辑页面

    正常的查询页面 正常页面可以通过以下图示中的符号进行上下调整 上三角点击完以后的展示页面 如下图 下三角点击完以后的展示页面 如下图 误触以后的页面 误触以后可以通过下图中标示的部分进行恢复 结果面板恢复 最大化区域图示 选择上图中红色框线

  • QT学习之个人编程规范

    每个人对语言的编程习惯都不一样 这里简单介绍一下自己在学习使用Qt时养成的编程习惯 仅供参考 1 命名规则 1 1 常规命名规则 1 1 1 类命名规则 适用对象 1 窗口控件实现类 所有之间或间接继承于QWidget类的实现类 规则 命名

  • OpenMP设置线程数及开启方法

    1 OpenMP线程数设置 通常我们希望并行线程数可以随着机器改变自适应的调整 网上介绍OpenMP的文章很多 但是很少提到该怎么分配线程数 一般来说线程数最大可以开到2 核心数 但是这样电脑计算资源就会被占用的过多 其他程序基本上会卡的不

  • ASP.NET Core WebAPI学习-6

    ASP NET Core WebAPI学习 1 ASP NET Core WebAPI学习 2 ASP NET Core WebAPI学习 3 ASP NET Core WebAPI学习 4 ASP NET Core WebAPI学习 5

  • 数据结构——图的广度优先遍历（BFS）

    本文内图的存储方式是邻接矩阵 不过BFS的具体实现代码与图的存储结构无关 BFS的遍历方法 与树的层次遍历几乎一样 在实现树的层次遍历时 需要找到结点的所有子结点 在实现BFS时 需要找到该结点的所有邻接点 所以在实现BFS之前 需要先学习

热门标签