java图搜索算法之DFS与BFS详解

java图搜索算法之DFS与BFS详解

目录一、前言二、深度优先搜索三、广度优先搜索四、结语

你好，我是小黄，一名独角兽企业的java开发工程师。

感谢茫茫人海中我们能够相遇，

俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习，

希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。

一、前言

上一篇文章我们提到了关于图的形象化描述方法，不知道大家还有没有印象。没有印象的话，可以去看一下上期的内容

对于图来说，搜索的方法无外乎两种，深度优先搜索（DFS）和广度优先搜索（BFS）

两种搜索算法也不太相同，今天我们就来看一下这两个搜索算法

二、深度优先搜索

我们一提到深度优先搜索，脑子里第一时间想到的就是递归

没错，深搜就是依靠递归的方法来进行的搜索，我们来看一个例题：

对于上图来说，使用深度优先搜索的路线为：0 -> 3 - > 2 -> 4 -> 5 -> 1

这里不懂深搜的小伙伴可以看下这篇：深度优先搜索

递归版本：

/**

* 深度优先搜索

*

* @param node

* @param set

*/

public void DFS(Node node, Set 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 stack = new Stack<>();

Set 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) {

uvUHTC return;

}

Queue queue = new LinkedList<>();

// 代表是否被使用

Set 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);

}

}

}

}

四、结语

这期的深度优先搜索和广度优先搜索比较简单

让你对图的搜索大概有个了解，下几期将会讲解一些真实的算法

在算法题中，题目不会单纯的让你求深搜和广http://搜，经常会和别的一起出现，比如最小生成树等

以上就是java数据结构图算法之DFS与BFS详解的详细内容，更多关于java数据结构图算法DFS与BFS的资料请关注我们其它相关文章！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。