java圖搜索算法之DFS與BFS詳解
你好，我是小黃，一名獨角獸企業(yè)的Java開發(fā)工程師。
感謝茫茫人海中我們能夠相遇，
俗話說：當你的才華和能力，不足以支撐你的夢想的時候，請靜下心來學習，
希望優(yōu)秀的你可以和我一起學習，一起努力，實現(xiàn)屬于自己的夢想。
一、前言
上一篇文章我們提到了關(guān)于圖的形象化描述方法，不知道大家還有沒有印象。沒有印象的話，可以去看一下上期的內(nèi)容
對于圖來說，搜索的方法無外乎兩種，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）
兩種搜索算法也不太相同，今天我們就來看一下這兩個搜索算法
二、深度優(yōu)先搜索
我們一提到深度優(yōu)先搜索，腦子里第一時間想到的就是遞歸
沒錯，深搜就是依靠遞歸的方法來進行的搜索，我們來看一個例題：
對于上圖來說，使用深度優(yōu)先搜索的路線為：0 -> 3 - > 2 -> 4 -> 5 -> 1
這里不懂深搜的小伙伴可以看下這篇：深度優(yōu)先搜索
遞歸版本：
/**
* 深度優(yōu)先搜索
*
* @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);
}
}
}
迭代版本：
/**
* 深度優(yōu)先搜索
*
* @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;
}
}
}
}
測試結(jié)果：
迭代版本：
0 3 2 4 5 1
遞歸版本：
0 3 2 4 5 1
三、廣度優(yōu)先搜索
對于廣度優(yōu)先搜索的話，簡單的來說，像走地圖一樣，一圈一圈的擴展開來
我們來看一個例題：
對于上圖來說，使用深度優(yōu)先搜索的路線為：0 -> 3 -> 1 -> 2 -> 4 -> 5
這里不懂廣搜的小伙伴可以看下這篇：廣度優(yōu)先搜索
/**
* 廣度優(yōu)先搜索
*
* @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);
}
}
}
}
四、結(jié)語
這期的深度優(yōu)先搜索和廣度優(yōu)先搜索比較簡單
讓你對圖的搜索大概有個了解，下幾期將會講解一些真實的算法
在算法題中，題目不會單純的讓你求深搜和廣搜，經(jīng)常會和別的一起出現(xiàn)，比如最小生成樹等
以上就是java數(shù)據(jù)結(jié)構(gòu)圖算法之DFS與BFS詳解的詳細內(nèi)容，更多關(guān)于java數(shù)據(jù)結(jié)構(gòu)圖算法DFS與BFS的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了java怎么連接并訪問activemq,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-07-07
這篇文章主要介紹了spring data redis的那些坑，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
MyBatis關(guān)聯(lián)查詢的實現(xiàn)
MyBatis可以通過定義多個表的關(guān)聯(lián)關(guān)系,實現(xiàn)多表查詢，本文主要介紹了MyBatis關(guān)聯(lián)查詢的實現(xiàn)，具有一定的參考價值，感興趣的可以了解一下2023-11-11
Java在指定路徑上創(chuàng)建文件提示不存在解決方法
在本篇文章里小編給大家整理的是一篇關(guān)于Java在指定路徑上創(chuàng)建文件提示不存在解決方法，有需要的朋友們可以參考下。2020-02-02
Java的SpringMVC中控制器返回XML數(shù)據(jù)問題
這篇文章主要介紹了Java的SpringMVC中控制器返回XML數(shù)據(jù)問題，控制器是處理HTTP請求的組件,它們接收來自客戶端的請求，并將其轉(zhuǎn)換為適當?shù)捻憫?這些響應可以是動態(tài)生成的?HTML?頁面，也可以是JSON或XML格式的數(shù)據(jù),需要的朋友可以參考下2023-07-07
Opitonal類就是Java提供的為了解決大家平時判斷對象是否為空用的。本文將通過示例為大家講解一下Optional類的使用，感興趣的可以收藏一下2022-12-12
這篇文章主要介紹了用java寫一個云端資源共享小程序,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-07-07
2010以上格式使用XSSFWorkBook對象, 2003格式使用HSSFWorkBook對象, 其他對象操作基本一樣，本文重點給大家介紹java使用poi生成excel的相關(guān)知識，感興趣的朋友一起看看吧2022-04-04
解決springboot 多線程使用MultipartFile讀取excel文件內(nèi)容報錯問題
這篇文章主要介紹了解決springboot 多線程使用MultipartFile讀取excel文件內(nèi)容報錯問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09
這篇文章主要介紹了如何用idea數(shù)據(jù)庫編寫快遞e站,本文通過圖文實例相結(jié)合給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01