# Java 深度優先搜索示例 > 原文： [https://javatutorial.net/depth-first-search-example-java](https://javatutorial.net/depth-first-search-example-java) 當涉及從 Java 中的給定數據結構訪問數據時，搜索和/或遍歷同樣重要。 圖和樹是可以使用不同方法搜索和/或遍歷的數據結構的示例。  深度優先搜索（簡稱 DFS）從一個未訪問的節點開始，然后開始選擇一個相鄰節點，直到沒有剩余節點為止。 執行完該“過程”之后，您將回溯到另一個選擇節點的選擇，如果沒有，則只需選擇另一個未訪問的節點即可。 ## 使用棧實現  上圖訪問的節點的順序為：5 10 25 30 35 40 15 20 ### 使用棧數據結構實現 DFS `Node.java`代表上圖中的每個“球”或“圓”。 它有一個**值** ，它代表每個球的“值”。 它也有一個名為`Visited`的布爾變量，顧名思義，它表示遍歷是否訪問了`Node`。 第三個實例變量`Node`類具有一個`ArrayList`，它表示當前節點與的所有相鄰節點（或相鄰節點）。 （如果您想了解有關`ArrayList`的更多信息，可以查看[本教程](https://javatutorial.net/java-arraylist-example)。） 就此類中的方法而言，有一個簡單的構造函數（該函數接受一個值并創建一個空的`ArrayList`），Setter 和 Getter 方法以及允許添加相鄰`Node`的方法。 `Node.java` ```java import java.util.*; public class Node{ private int val; private boolean visited; private List<Node> adjecents; public Node(int val) { this.val = val; this.adjecents = new ArrayList<>(); } public void addAdjecents(Node n) { this.adjecents.add(n); } public List<Node> getAdjacenets() { return adjecents; } public int getVal() { return this.val; } public boolean isVisited() { return this.visited; } public void setVal(int v) { this.val = v; } public void setVisited(boolean visited) { this.visited = visited; } } ``` `DFS.java` 此類只有一種方法：解決方案。 它使用棧數據結構，并以節點為元素。 它將指定的元素添加到節點，然后將其標記為已訪問。 在那之后，有一個`while`循環，不斷檢查棧是否為空。 如果不是，則從棧中刪除一個元素，獲取要刪除的元素的鄰居。 然后，存在另一個循環，其目的是將每個鄰居節點標記為已訪問，并將該鄰居節點添加到棧中。 ```java import java.util.*; public class DFS { public void stackSolution(Node node) { Stack<Node> DFS_stack = new Stack<Node>(); DFS_stack.add(node); node.setVisited(true); while (!DFS_stack.isEmpty()) { Node nodeRemove = DFS_stack.pop(); System.out.print(nodeRemove.getVal() + " "); List<Node> adjs = nodeRemove.getAdjacenets(); for (int i = 0; i < adjs.size(); i++) { Node currentNode = adjs.get(i); if(currentNode != null && !currentNode.isVisited()) { DFS_stack.add(currentNode); currentNode.setVisited(true); } } } } } ``` `Main.java` 在此類中，主要方法是創建`Node`類的 8 個實例并傳遞一些值。 （請記住，下面的示例使用上圖（圖像）。我們將不同的節點作為鄰居添加到不同的節點。此后，我們從`node5`開始并遍歷它）。 ```java import java.util.*; public class Main { public static void main(String [] args) { Node node5 = new Node(5); Node node10 = new Node(10); Node node15 = new Node(15); Node node20 = new Node(20); Node node25 = new Node(25); Node node30 = new Node(30); Node node35 = new Node(35); Node node40 = new Node(40); node5.addAdjecents(node10); node10.addAdjecents(node15); node15.addAdjecents(node20); node10.addAdjecents(node25); node25.addAdjecents(node35); node35.addAdjecents(node40); node25.addAdjecents(node30); DFS demo = new DFS(); System.out.println("DFS traversal of above graph: "); demo.stackSolution(node5); } } ``` **輸出**： ```java DFS traversal of above graph: 5 10 25 30 35 40 15 20 ```