java图搜索算法之DFS与BFS详解
作者:爱敲代码的小黄 发布时间:2022-08-15 15:48:57
标签:图搜索,DFS,BFS
你好,我是小黄,一名独角兽企业的Java开发工程师。
感谢茫茫人海中我们能够相遇,
俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习,
希望优秀的你可以和我一起学习,一起努力,实现属于自己的梦想。
一、前言
上一篇文章我们提到了关于图的形象化描述方法,不知道大家还有没有印象。没有印象的话,可以去看一下上期的内容
对于图来说,搜索的方法无外乎两种,深度优先搜索(DFS)和广度优先搜索(BFS)
两种搜索算法也不太相同,今天我们就来看一下这两个搜索算法
二、深度优先搜索
我们一提到深度优先搜索,脑子里第一时间想到的就是递归
没错,深搜就是依靠递归的方法来进行的搜索,我们来看一个例题:
对于上图来说,使用深度优先搜索的路线为:0 -> 3 - > 2 -> 4 -> 5 -> 1
这里不懂深搜的小伙伴可以看下这篇:深度优先搜索
递归版本:
/**
* 深度优先搜索
*
* @param node
* @param set
*/
public void DFS(Node node, Set<Node> set) {
if (node == null) {
return;
}
if (!set.contains(node)) {
set.add(node);
System.out.print(node.value + " ");
for (Node node1 : node.nexts) {
DFS(node1, set);
}
}
}
迭代版本:
/**
* 深度优先搜索
*
* @param node
*/
public void DFS(Node node) {
Stack<Node> stack = new Stack<>();
Set<Node> set = new HashSet<>();
stack.add(node);
set.add(node);
System.out.print(node.value + " ");
while (!stack.isEmpty()) {
Node cur = stack.pop();
for (Node next : cur.nexts) {
if (!set.contains(next)) {
stack.add(cur); // 用来做记忆化的
stack.add(next);
System.out.print(next.value + " ");
set.add(next);
break;
}
}
}
}
测试结果:
迭代版本:
0 3 2 4 5 1
递归版本:
0 3 2 4 5 1
三、广度优先搜索
对于广度优先搜索的话,简单的来说,像走地图一样,一圈一圈的扩展开来
我们来看一个例题:
对于上图来说,使用深度优先搜索的路线为:0 -> 3 -> 1 -> 2 -> 4 -> 5
这里不懂广搜的小伙伴可以看下这篇:广度优先搜索
/**
* 广度优先搜索
*
* @param node
*/
public static void BFS(Node node) {
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
// 代表是否被使用
Set<Node> set = new HashSet<>();
queue.add(node);
set.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur.value + " ");
for (Node next : cur.nexts) {
if (!set.contains(next)) {
queue.add(next);
set.add(next);
}
}
}
}
四、结语
这期的深度优先搜索和广度优先搜索比较简单
让你对图的搜索大概有个了解,下几期将会讲解一些真实的算法
在算法题中,题目不会单纯的让你求深搜和广搜,经常会和别的一起出现,比如最小生成树等
来源:https://blog.csdn.net/qq_40915439/article/details/120802924
0
投稿
猜你喜欢
- <%@ page language="java" contentType="text/html; cha
- 前言目前正在做的项目,为了增加用户的体验度,准备增加一些动画效果,其中底部栏中间按钮的点击事件参考了闲鱼的动效,便在此基础上仿写了该动效,并
- SpringBoot2之PUT请求接收不了参数的解决办法,这个问题,关乎两个Filter过滤器,是spring3和3.5之后提供的,目的就是
- 前言本文主要给大家介绍了关于Spring Boot优化内嵌Tomcat的相关内容,分享出来供大家参考学习,下面话不多说了,来一看看详细的介绍
- (注意:本文基于JDK1.8)前言元素在存储到内存中,当我们需要使用在内存中存储的元素,这就涉及到在内存中查找元素,今天一起学习Vector
- 之前写过一篇获取properties文件里面的值:Springboot 指定获取自己写的配置properties文件的值www.jb51.n
- web.xml中设置:<servlet> <servlet-name>DisplayChart</servle
- 本文实例为大家分享了C语言实现扫雷游戏的具体代码,供大家参考,具体内容如下前言一、游戏规则介绍扫雷是一个十分经典的游戏,一张棋盘中有很多个不
- 第一次写上传图片的代码,碰到很多问题。昨天做了整整一天,终于在晚上的时候成功了。大声欢呼。但是,做完之后,还是有很多问题想不通。所以在这里也
- 本文实例为大家分享了java数据库唯一id生成工具类的具体代码,供大家参考,具体内容如下import java.io.File;import
- 本文实例讲述了java实现递归文件列表的方法。分享给大家供大家参考。具体如下:FileListing.java如下:import java.
- 井字棋游戏要求在3乘3棋盘上,每行都相同或者每列都相同再或者对角线相同,则胜出.因此我们可以使用一个二维数组来表示棋盘,判断胜负只需要判断数
- Spring Boot 的启动原理可以概括为以下几个步骤:加载 Spring Boot 应用程序的启动类根据启动类所在的包路径扫描相关的类根
- 1 什么是class对象类是程序的一部分,每个类都有一个class对象。换言之,每当编写并且编译了一个新类,就会产生一个class对象(更恰
- 常见Bean后处理器的作用:public static void main(String[] args) { &
- 1、需要引入依赖<dependency> &l
- 这篇文章主要介绍了Java编码摘要算法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参
- 写在前面,在笔者完成这个demo的时候,笔者发现现在大家已经不用Ajax来完成联级菜单了,实际上笔者这个demo也并不是为了完成这个,笔者主
- IO流Java中IO流分为两种,字节流和字符流,顾名思义字节流就是按照字节来读取和写入的,字符刘是按照字符来存取的;常用的文件读取用的就是字
- 在 Flutter 中使用图片是最基础能力之一。作为春节开工后的第一篇文章,17 做了精心准备,满满的都是干货!本文介绍如何在 Flutte