點選左上角藍字，關注“鍋外的大佬”
專注分享國外最新技術内容
1. 概述
在本教程中，我們将探讨Java中的深度優先搜尋
深度優先搜尋(DFS)是一個應用于樹、圖等資料結構的周遊算法。在移動到下一個分支之前，深度優先搜尋會 深度為優先原則去探索新的分支。
在接下來的部分中，我們将首先了解樹的實作，然後是圖。
要了解如何在Java中實作這些結構，請檢視我們以前的關于 二叉樹 Binary Tree 和 圖 Graph 的教程。
2. 樹的深度優先搜尋
使用 DFS 周遊樹有三種不同的順序：
- 先序周遊
- 中序周遊
- 後序周遊
2.1 先序周遊
在先序周遊中，先周遊其根節點，依次是左子樹和右子樹。
使用遞歸簡單地實作先序周遊：
- 通路目前節點
- 周遊左子樹
- 周遊右子樹
public void traversePreOrder(Node node) { if (node != null) { visit(node.value); traversePreOrder(node.left); traversePreOrder(node.right); }}
使用非遞歸方式實作先序周遊：
- 将根節點入棧
- 當棧不為空
- 将目前節點(棧頂元素)彈棧
- 通路目前節點
- 依次将目前節點右子節點、左子節點入棧
public void traversePreOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(!stack.isEmpty()) { current = stack.pop(); visit(current.value); if(current.right != null) { stack.push(current.right); } if(current.left != null) { stack.push(current.left); } } }
2.2 中序周遊
對于中序周遊，先通路其左子樹，然後根節點，最後通路右子樹。
二叉搜尋樹的中序周遊意味着按值的遞增順序周遊節點。
使用遞歸實作中序周遊：
public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); visit(node.value); traverseInOrder(node.right); }}
同時也可以使用非遞歸實作中序周遊：
- 将根節點壓棧
- 當棧不為空
- 繼續将左子節點壓棧，直到目前節點為最左節點(即無左子節點)
- 通路目前節點
- 将右子節點壓棧
public void traverseInOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(! stack.isEmpty()) { while(current.left != null) { current = current.left; stack.push(current); } current = stack.pop(); visit(current.value); if(current.right != null) { current = current.right; stack.push(current); } }}
2.3 後序周遊
最後，在後序周遊中，在通路根節點之前，依次先通路左子節點、右子節點。
參考前邊，遞歸實作後序周遊：
public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); visit(node.value); }}
使用非遞歸實作後序周遊：
- 将根節點入棧
- 當棧不為空
- 檢查是否已經周遊了左子樹和右子樹
- 如果沒有，則将右子節點和左子節點壓棧
public void traversePostOrderWithoutRecursion() { Stack stack = new Stack(); Node prev = root; Node current = root; stack.push(root); while (!stack.isEmpty()) { current = stack.peek(); boolean hasChild = (current.left != null || current.right != null); boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); if (!hasChild || isPrevLastChild) { current = stack.pop(); visit(current.value); prev = current; } else { if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } } }
3. 圖的深度優先搜尋
圖和樹之間的主要差別在于圖可能包含循環。
是以，為了避免循環搜尋，我們将在通路每個節點時對其進行标記。
接下來将會展示圖DFS的遞歸、非遞歸實作。
3.1 圖的DFS遞歸實作
首先，讓我們從遞歸開始：
- 從一個任意的節點開始
- 标記目前節點為已通路
- 通路目前節點
- 周遊未通路的相鄰節點
public void dfs(int start) { boolean[] isVisited = new boolean[adjVertices.size()]; dfsRecursive(start, isVisited);} private void dfsRecursive(int current, boolean[] isVisited) { isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) dfsRecursive(dest, isVisited); }}
3.2 圖的DFS非遞歸實作
也可以在不使用遞歸的情況下實作圖的DFS。我們也需要使用一個棧進行實作：
- 将從一個任意的節點開始
- 将節點壓棧
- 當棧不為空
- 标記目前節點為已通路
- 通路目前節點
- 将未通路的相鄰頂點壓棧
public void dfsWithoutRecursion(int start) { Stack stack = new Stack(); boolean[] isVisited = new boolean[adjVertices.size()]; stack.push(start); while (!stack.isEmpty()) { int current = stack.pop(); isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) stack.push(dest); } }}
3.3 拓撲排序
圖的深度優先搜尋有很多應用。拓撲排序是深度優先搜尋最著名的應用之一。
有向圖的拓撲排序是其頂點的線性排序，是以對于每個邊，源節點都位于目标之前。
要進行拓撲排序，需要對剛剛實作的DFS進行簡單的改造：
- 我們需要将通路的頂點保持在堆棧中，因為拓撲排序是以相反的順序通路的頂點
- 隻有在周遊所有相鄰節點之後，才會将通路的節點推送到堆棧中。
public List topologicalSort(int start) { LinkedList result = new LinkedList(); boolean[] isVisited = new boolean[adjVertices.size()]; topologicalSortRecursive(start, isVisited, result); return result;} private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList result) { isVisited[current] = true; for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) topologicalSortRecursive(dest, isVisited, result); } result.addFirst(current);}
4. 結論
在本文中，我們讨論了樹和圖的深度優先搜尋。
完整代碼見 GitHub 。
●誰說搞Java的不能玩機器學習？
●Spring Boot 配置中繼資料指南
●
右上角按鈕分享給更多人哦~
來都來了，點個在看再走吧~~~