图的遍历算法——BFS和DFS

一、前言

在计算机科学领域,图是一种非常重要的数据结构。图是由节点和边构成的,节点之间的关系通过边来表示。图的遍历是对图进行搜索的过程,可以帮助我们找到图中的所有节点和边。

在本文中,我们将介绍两种常见的图遍历算法——BFS和DFS。BFS(广度优先搜索)是一种广度优先搜索算法,DFS(深度优先搜索)是一种深度优先搜索算法。这两种算法都可以用来遍历图中的所有节点和边,但它们的搜索方式不同。

二、BFS算法

BFS算法是一种广度优先搜索算法,它从图的起始节点开始遍历,逐层扩展搜索范围,直到找到目标节点为止。BFS算法使用队列来存储待搜索的节点,先进先出的原则确保了搜索的广度优先。

2.1 算法思路

BFS算法的基本思路如下:

  1. 将起始节点放入队列中,并将其标记为已访问。
  2. 从队列中取出一个节点,访问它的所有未访问过的邻居节点,并将它们放入队列中。
  3. 重复步骤2,直到队列为空。

2.2 代码实现

下面是BFS算法的Java代码实现:

public class Code01_BFS {/*** BFS算法* @param start 起始节点*/public static void bfs(Node start) {if (start == null) {return;}Queue<Node> queue = new LinkedList<>();Set<Node> set = new HashSet<>();queue.add(start);set.add(start);while (!queue.isEmpty()) {Node cur = queue.poll();System.out.println(cur.value);for (Node next : cur.nexts) {if (!set.contains(next)) {set.add(next);queue.add(next);}}}}
}

三、DFS算法

DFS算法是一种深度优先搜索算法,它从图的起始节点开始遍历,一直走到最深处,直到找到目标节点为止。DFS算法使用栈来存储待搜索的节点,后进先出的原则确保了搜索的深度优先。

3.1 算法思路

DFS算法的基本思路如下:

  1. 将起始节点压入栈中,并将其标记为已访问。
  2. 从栈中弹出一个节点,访问它的所有未访问过的邻居节点,并将它们压入栈中。
  3. 重复步骤2,直到栈为空。

3.2 代码实现

下面是DFS算法的Java代码实现:

public class Code02_DFS {/*** DFS算法* @param node 起始节点*/public static void dfs(Node node) {if (node == null) {return;}Stack<Node> stack = new Stack<>();HashSet<Node> set = new HashSet<>();stack.add(node);set.add(node);while (!stack.isEmpty()) {Node cur = stack.pop();for (Node next : cur.nexts) {if (!set.contains(next)) {stack.push(cur);stack.push(next);set.add(next);System.out.println(next.value);break;}}}}
}

四、总结

本文介绍了两种常见的图遍历算法——BFS和DFS。BFS算法使用队列来存储待搜索的节点,先进先出的原则确保了搜索的广度优先;DFS算法使用栈来存储待搜索的节点,后进先出的原则确保了搜索的深度优先。这两种算法都可以用来遍历图中的所有节点和边,具体使用哪种算法取决于具体的问题和需求。

希望本文能够帮助大家更好地理解图的遍历算法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/143360.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

使用低代码实现一个表单页面 ------ XinBuilder

平台介绍 如果你不是一个前端开发&#xff0c;但是想要实现出一个前端页面。 那么就可以通过低代码的方式&#xff0c;拖拽和配置出你想要的页面。 而XinBuilder就是简单的一套低代码平台&#xff0c;你可以在上面拖拽出自己想要使用的组件并进行配置。使用方式也很简单。 这…

影刀自动化采集底层逻辑

hello,大家好&#xff0c;这里是【玩数据的诡途】 接上回 <我的影刀故事> 今天给大家介绍一下整个采集的底层逻辑&#xff0c;包括业务流程自动化也是基于这一套基础逻辑进行展开的&#xff0c;顺便带大家熟悉一下影刀&#xff0c;既然叫影刀系列了&#xff0c;那后续一些…

【100天精通Python】Day65:Python可视化_Matplotlib3D绘图mplot3d,绘制3D散点图、3D线图和3D条形图,示例+代码

1 mpl_toolkits.mplot3d 功能介绍 mpl_toolkits.mplot3d 是 Matplotlib 库中的一个子模块&#xff0c;用于绘制和可视化三维图形&#xff0c;包括三维散点图、曲面图、线图等。它提供了丰富的功能来创建和定制三维图形。以下是 mpl_toolkits.mplot3d 的主要功能和功能简介&am…

服务断路器_Resilience4j信号量隔离实现

POM引入依赖 <dependency><groupId>io.github.resilience4j</groupId><artifactId>resilience4j-bulkhead</artifactId><version>1.7.0</version> </dependency>信号量隔离修改YML文件 resilience4j:#信号量隔离bulkhead:ins…

支撑电动汽车规模化,特来电智能化升级群充产品

9月26日&#xff0c;中国领先的充电网生态运营商特来电重磅发布智能群充4.0产品&#xff0c;标志着特来电群充产品体系进一步升级&#xff0c;充电行业迎来更高质量、更高性能的设备与系统&#xff0c;充电网基础设施将更好地支撑大规模电动汽车的发展。 群充技术路线引领充电…

Element UI搭建首页导航和左侧菜单以及Mock.js和(组件通信)总线的运用

目录 前言 一、Mock.js简介及使用 1.Mock.js简介 1.1.什么是Mock.js 1.2.Mock.js的两大特性 1.3.Mock.js使用的优势 1.4.Mock.js的基本用法 1.5.Mock.js与前端框架的集成 2.Mock.js的使用 2.1安装Mock.js 2.2.引入mockjs 2.3.mockjs使用 2.3.1.定义测试数据文件 2…

程序员不得不知道的排序算法-上

目录 前言 1.冒泡排序 2.选择排序 3.插入排序 4.希尔排序 5.快速排序 6.归并排序 总结 前言 今天给大家讲一下常用的排序算法 1.冒泡排序 冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法&#xff0c;它重复地从待排序的元素中比较相邻的两个元素&a…

Java中的IO流的缓冲流

不爱生姜不吃醋⭐️ 如果本文有什么错误的话欢迎在评论区中指正 与其明天开始&#xff0c;不如现在行动&#xff01; 文章目录 &#x1f334;IO流体系结构&#x1f334;缓冲流1.提高效率的原理2.缓冲流的类型3.字符缓冲流两个特有方法 &#x1f334;总结 &#x1f334;IO流体系…

硬件系统工程师宝典(42)-----耦合电容如何布局?

各位同学大家好&#xff0c;欢迎继续做客电子工程学习圈&#xff0c;今天我们继续来讲这本书&#xff0c;硬件系统工程师宝典。 上篇我们说到了对时序有要求的系统中如何正确使用蛇形走线&#xff0c;可以增加信号的延时&#xff0c;符合系统的时序要求。今天来说说电容去耦的…

三、VXLAN静态方式实验举例

VXLAN静态方式实验举例 1.1、静态方式部署集中式网关1.1.1、VXLAN隧道建立1.1.2、MAC地址动态学习1.1.3、同子网已知单播报文转发1.1.4、同子网BUM报文转发1.1.5、跨子网报文转发1.1.6、配置VXLAN接入业务部署方式 1.2、配置举例&#xff0c;相同网段互通&#xff08;静态方式&…

(数组/字符串) 380. O(1) 时间插入、删除和获取随机元素 ——【Leetcode每日一题】

❓ 380. O(1) 时间插入、删除和获取随机元素 难度&#xff1a;中等 实现 RandomizedSet 类&#xff1a; RandomizedSet() 初始化 RandomizedSet 对象bool insert(int val) 当元素 val 不存在时&#xff0c;向集合中插入该项&#xff0c;并返回 true &#xff1b;否则&#x…

【Maven入门篇】(1)详细讲解Maven的安装报错解决

&#x1f38a;专栏【Maven入门篇】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【The truth that you leave】 &#x1f970;欢迎并且感谢大家指出我的问题 文章目录 &#x1f33a;Maven介绍⭐作用⭐官网 &#x1f384;maven安…

【C语言】文件操作(一)

前言 本篇博客讲解对文件的操作&#xff0c;包括打开&#xff0c;关闭操作。在下篇博客将讲解文件的读写。 文章目录 一、 什么是文件&#xff1f;1.1 用于存储数据1.2 文件类型1.3 文件名1.4 二进制文件和文本文件 二、文件的打开和关闭2.1 流和标准流2.2 文件指针2.3文件的打…

asp.net core automapper的使用

1.安装automapper的nuget包 AutoMapper.Extensions.Microsoft.DependencyInjection 2.创建需要映射的类和转换后的类 public class studto{public int sn { get; set; }public string name { get; set; }public string sex { get; set; }public int age { get; set; }public s…

前端的多种克隆方式和注意事项

克隆的意义和常见场景: 意义: 保证原数据的完整性和独立性常见场景: 复制数据, 函数入参, class构造函数等 浅克隆: 对象常用的浅克隆 es6扩展运算符...Object.assign 数组常用的浅克隆 es6的扩展运算符...slice>arr.slice(0)[].concat 深度克隆: 克隆对象的每个层级如…

如何套用模板制作大屏?

在山海鲸可视化的资源中心里内置了大量的二维、三维大屏模板&#xff0c;大家可以根据需要找到自己想要的模板&#xff0c;然后点击下载直接进行使用。 有需要可自行前往哔哩哔哩账号中观看相关内容的视频教程↓↓↓ 山海鲸可视化的个人空间-山海鲸可视化个人主页-哔哩哔哩视频…

NodeMCU ESP8266基于Arduino IDE的开发环境搭建(图文并茂)

文章目录 NodeMCU ESP8266基于Arduino IDE的开发环境搭建&#xff08;手把手教程&#xff09;软件下载官网地址百度云 安装IDE配置基础配置设置开发板 测试串口驱动下载测试用例 总结 NodeMCU ESP8266基于Arduino IDE的开发环境搭建&#xff08;手把手教程&#xff09; 软件下…

安卓备份基带分区 备份字库 步骤解析 以免误檫除分区或者“格机” 后悔莫及

玩机搞机---安卓机型mtk和高通芯片查看分区 导出分区 备份分区的一些工具分析 修复基带 改串码 基带qcn 改相关参数 格机危害 手机基带的重要性前面几期博文我都有相关的说明。他区别于别的分区。而且目前手机的安全性越来越高。基带分区基本都是专机专用。而不像早期机型一…

jvm深入研究文档--jvm分区以及职责

Java虚拟机&#xff08;JVM&#xff09;主要包括以下几个区域&#xff1a; 方法区&#xff08;Method Area&#xff09;&#xff1a;这个区域存储已被加载的类信息&#xff0c;常量&#xff0c;静态变量&#xff0c;即时编译器编译后的代码等数据。方法区是所有线程共享的。在…

uniapp:不同权限设置不同的tabBar

1、在pages.json里&#xff0c;将所有tabBar涉及的页面都加进来。 我这里使用username来动态显示tabBar。 jeecg用户显示&#xff1a;首页&#xff0c;订单&#xff0c;消息&#xff0c;发现&#xff0c;我的&#xff0c;一共5个tabBar。 admin用户显示&#xff1a;首页&…