深度优先(DFS)和广度优先(BFS)——算法

2024-09-09 04:32
文章标签 算法 深度 bfs dfs 优先 广度

本文主要是介绍深度优先(DFS)和广度优先(BFS)——算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

深度优先

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。

沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。----《维基百科》

广度优先

广度优先搜索算法(Breadth First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。

简单的说,广度优先搜索算法是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。借助广度优先搜索算法,可以让你找出两样东西之间的最短距离。

比较

  • 拿谚语打比方的话,深度优先搜索可以比作打破砂锅问到底、不撞南墙不回头;广度优先搜索则对应广撒网,多敛鱼
  • 两者没有绝对的优劣之分,只是适用场景不同
  • 当解决方案离树根不远或搜索深度可变时,BFS通常更好,因为只需搜索所有数据中的一部分。另外BFS的一个重要优点是它可以用于找到无权图(有权图用Dijkstra算法,贪心思想)中任意两个节点之间的最短路径(不能使用DFS)
  • 如果树比较宽而且深度有限,DFS可能是更优选项,因为DFS比BSF更节省空间,另外由于使用递归,DFS更好写(BFS必须手动维护队列)
时间复杂度

都是O(n)

空间复杂度

都是O(n)

参考

  • https://www.cnblogs.com/nkqlhqc/p/10878643.html
  • https://cloud.tencent.com/developer/article/1156139
  • https://zhuanlan.zhihu.com/p/125767384

java实现

深度优先
public class DepthFirstSearch {private int[] a, book;private int n;private int total;public DepthFirstSearch(int n) {a = new int[n + 1];book = new int[n + 1];this.n = n;total = 0;}private void dfs(int step) {if (step == n + 1) {for (int i = 1; i < a.length; i++) {System.out.print(a[i] + "\t");}System.out.println();total++;}for (int i = 1; i <= n; i++) {if (book[i] == 0) {a[step] = i;book[i] = 1;dfs(step + 1);book[i] = 0;}}}public static void main(String[] args) {DepthFirstSearch depthFirstSearch = new DepthFirstSearch(4);depthFirstSearch.dfs(1);System.out.println("total: " + depthFirstSearch.getTotal());}public int getTotal() {return total;}
}
广度优先
public class BreadthFirstSearch {Note que[] = new Note[2501];int a[][] = new int[51][51];int book[][] = new int[51][51];//方向int next[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int head, tail;int k, n, m, startX, startY, p, q, tx, ty, flag;public void init() {//起始位置startX = 1;startY = 1;//目标位置p = 9;q = 9;//地图大小n = 10;m = 10;}public void find() {//队列初始化head = 1;tail = 1;//往队列插入迷宫入口坐标que[tail] = new Note();que[tail].x = startX;que[tail].y = startY;que[tail].f = 0;que[tail].s = 0;tail++;book[startX][startY] = 1;//用来标记是否到达目标点,0表示没有达到,1表示达到flag = 0;while (head < tail) {for (k = 0; k <= 3; k++) {tx = que[head].x + next[k][0];ty = que[head].y + next[k][1];//越界判断if (tx < 1 || tx > n || ty < 1 || ty > m) {continue;}//障碍物,是否在路径中判断if (a[tx][ty] == 0 && book[tx][ty] == 0) {//已经走过book[tx][ty] = 1;//插入新的点到队列中que[tail] = new Note();que[tail].x = tx;que[tail].y = ty;que[tail].f = head;que[tail].s = que[head].s + 1;tail++;}//如果到目标点了,停止扩展,任务结束,退出循环if (tx == p && ty == q) {flag = 1;break;}}if (flag == 1) {break;}//注意这地方千万不要忘记,当一个点扩展结束后,head++才能对后面的点进行扩展head++;}}public void print() {System.out.println(que[tail - 1].s);}public static void main(String[] args) {BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch();breadthFirstSearch.init();breadthFirstSearch.find();breadthFirstSearch.print();}public static class Note {//横坐标int x;//纵坐标int y;//父亲在队列中的编号int f;//步数int s;}
}

这篇关于深度优先(DFS)和广度优先(BFS)——算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1