java图搜索算法之DFS与BFS详解
作者:爱敲代码的小黄 时间:2022-08-15 15:48:57
你好,我是小黄,一名独角兽企业的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
标签:图搜索,DFS,BFS
0
投稿
猜你喜欢
详解Java设计模式编程中的中介者模式
2021-09-24 02:48:54
详解C# Socket异步通信实例
2022-08-27 14:27:22
Android中判断网络是否连接实例详解
2023-10-19 11:45:39
OpenHarmony实现屏幕亮度动态调节方法详解
2022-01-13 18:24:08
SWT(JFace)体验之复制粘贴
2022-11-18 13:47:46
Android录制按钮源码解析
2022-06-24 19:24:44
Android开发之模仿微信打开网页的进度条效果(高仿)
2021-09-02 10:17:04
C#文件和字节流的转换方法
2022-03-18 05:39:43
Java面试题之HashMap 的 hash 方法原理是什么
2022-09-11 20:20:54
java 线程锁详细介绍及实例代码
2022-03-16 13:50:45
Kotlin协程Context应用使用示例详解
2023-07-10 08:25:16
Android为Tiny4412设备驱动在proc目录下添加一个可读版本信息的文件
2022-09-24 05:37:20
java中form以post、get方式提交数据中文乱码问题总结
2022-12-15 06:53:59
C#实现自由组合本地缓存、分布式缓存和数据查询
2021-06-13 00:56:11
Android开发中Activity之间切换出现短暂黑屏的解决方法
2023-02-19 04:29:38
C#语言主要特性总结
2021-07-16 07:59:43
C#中实现任意List的全组合算法代码
2022-09-23 01:06:48
C#中Equality和Identity浅析
2022-10-11 10:43:38
C# 函数覆盖总结学习(推荐)
2021-12-27 00:33:05
flutter中的资源和图片加载示例详解
2023-08-24 13:19:39