java图搜索算法之DFS与BFS详解
程序员文章站
2022-04-10 12:51:40
目录一、前言二、深度优先搜索三、广度优先搜索四、结语你好,我是小黄,一名独角兽企业的java开发工程师。感谢茫茫人海中我们能够相遇,俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习,...
你好,我是小黄,一名独角兽企业的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); } } } }
四、结语
这期的深度优先搜索和广度优先搜索比较简单
让你对图的搜索大概有个了解,下几期将会讲解一些真实的算法
在算法题中,题目不会单纯的让你求深搜和广搜,经常会和别的一起出现,比如最小生成树等
以上就是java数据结构图算法之dfs与bfs详解的详细内容,更多关于java数据结构图算法dfs与bfs的资料请关注其它相关文章!
下一篇: 我完全不相信这是我媳妇