# 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
```
- JavaTutorialNetwork 中文系列教程
- Java 基礎
- Java 概述
- 在 Ubuntu 上安裝 Java 8 JDK
- Java Eclipse 教程
- Eclipse 快捷方式
- 簡單的 Java 示例
- Java 基本類型
- Java 循環
- Java 數組
- Java 讀取文件示例
- Java 對象和類教程
- 什么是面向對象編程(OOP)
- Java 封裝示例
- Java 接口示例
- Java 繼承示例
- Java 抽象示例
- Java 多態示例
- Java 中的方法重載與方法覆蓋
- Java 控制流語句
- Java 核心
- 如何在 Windows,Linux 和 Mac 上安裝 Maven
- 如何使用 Maven 配置文件
- 如何將自定義庫包含到 Maven 本地存儲庫中
- 如何使用 JUnit 進行單元測試
- 如何使用 Maven 運行 JUnit 測試
- 如何在 Java 中使用 Maven 創建子模塊
- 如何使用 Maven 創建 Java JAR 文件
- 如何使用 Maven 創建 Java WAR 文件
- JVM 解釋
- Java 內存模型解釋示例
- 捕獲 Java 堆轉儲的前 3 種方法
- Java 垃圾收集
- Java 互斥量示例
- Java 信號量示例
- Java 并行流示例
- Java 線程同步
- Java 線程池示例
- Java ThreadLocal示例
- Java 中的活鎖和死鎖
- Java Future示例
- Java equals()方法示例
- Java Lambda 表達式教程
- Java Optional示例
- Java 11 HTTP 客戶端示例
- Java 類加載器介紹
- Java 枚舉示例
- Java hashCode()方法示例
- 如何測試獨立的 Java 應用程序
- SWING JFrame基礎知識,如何創建JFrame
- Java SWING JFrame布局示例
- 在JFrame上顯示文本和圖形
- 與JFrame交互 – 按鈕,監聽器和文本區域
- 如何使用 Maven 創建 Java JAR 文件
- Java Collection新手指南
- 選擇合適的 Java 集合
- Java ArrayList示例
- Java LinkedList示例
- Java HashSet示例
- Java TreeSet示例
- Java LinkedHashSet示例
- Java EnumSet示例
- Java ConcurrentHashSet示例
- Java HashMap示例
- Java LinkedHashMap示例
- Java TreeMap示例
- Java EnumMap示例
- Java WeakHashMap示例
- Java IdentityHashMap示例
- Java SortedMap示例
- Java ConcurrentMap示例
- Java Hashtable示例
- Java 中ArrayList和LinkedList之間的區別
- Java HashMap迭代示例
- Java HashMap內聯初始化
- Java 中HashMap和TreeMap之間的區別
- Java 圖示例
- Java 深度優先搜索示例
- Java 廣度優先搜索示例
- 不同的算法時間復雜度
- Java 序列化示例
- Java 反射示例
- Java 中的弱引用
- Java 8 日期時間 API
- Java 基本正則表達式
- 使用 Java 檢索可用磁盤空間
- Java 生成 MD5 哈希和
- Java 增加內存
- Java 屬性文件示例
- 如何在 Eclipse 上安裝 Java 9 Beta
- Java 9 JShell 示例
- Java 9 不可變列表示例
- Java 9 不可變集示例
- Java 9 不可變映射示例
- Java 單例設計模式示例
- Java 代理設計模式示例
- Java 觀察者設計模式示例
- Java 工廠設計模式
- Java 構建器設計模式
- Java 比較器示例
- Java 發送電子郵件示例
- Java volatile示例
- Java Docker 和 Docker 容器簡介
- 安裝和配置 MySQL 數據庫和服務器以供 Spring 使用
- 如何在 Java 中使用 MySQL 連接器
- 如何使用 Eclipse 調試 Java
- Java EE
- 如何在 Windows 10 中設置JAVA_HOME
- JavaBeans 及其組件簡介
- 如何安裝和配置 Tomcat 8
- 如何在 Tomcat 中部署和取消部署應用程序
- 從 Eclipse 運行 Tomcat
- Java Servlet 示例
- Java Servlet POST 示例
- Servlet 請求信息示例
- Servlet 注解示例
- 使用初始化參數配置 Java Web 應用程序
- Java Servlet 文件上傳
- Java JSP 示例
- Glassfish 啟用安全管理
- 如何使用 MySQL 配置 Glassfish 4
- Java 文件上傳 REST 服務
- Glassfish 和 Jetty 的 Java WebSockets 教程
- 基于 Glassfish 表單的身份驗證示例
- 如何使用 Java EE 和 Angular 構建單頁應用程序
- Spring
- 在 Eclipse 中安裝 Spring STS
- 使用 STS 創建簡單的 Spring Web App
- Spring Web Framework 簡介
- Java Docker 和 Docker 容器簡介
- 在 Spring 中實現控制器
- Spring 中的PathVariable注解
- Spring 中的RequestBody注解
- Spring 中的RequestParam注解
- Spring 攔截器
- Spring IOC
- Java Spring IoC 容器示例
- Spring 中的DispatcherServlet
- Spring 示例中的依賴注入
- 實現 Spring MVC 控制器
- Spring ORM 簡介
- 什么是 DAO 以及如何使用它
- 如何對 DAO 組件進行單元測試
- 如何對控制器和服務執行單元測試
- 安裝和配置 MySQL 數據庫和服務器以供 Spring 使用
- 如何在 Spring 中處理登錄身份驗證
- Spring Security 簡介及其設置
- 如何使用 Spring 創建 RESTful Web 服務
- Spring CSRF 保護
- Spring 中基于 OAuth2 的身份驗證和授權
- Spring Boot 簡介
- Spring MVC 框架介紹
- Spring JDBC 簡介
- 如何 docker 化 Spring 應用程序
- Spring 的@Autowired注解
- Spring AOP 中的核心概念和建議類型
- Sping Bean 簡介
- 如何在 Java 中使用 MySQL 連接器
- 安卓
- 安裝和配置 Android Studio
- 將 Android 設備連接到 Android Studio
- Android 簡介,活動,意圖,服務,布局
- 創建一個簡單的 Android 應用
- 運行和調試 Android 應用程序
- 在虛擬設備上運行 Android 應用程序
- Android 活動示例
- Android 意圖示例
- Android 服務示例
- Android 線性布局示例
- Android 相對布局示例
- Android Web 視圖示例
- Android 列表視圖示例
- Android 網格視圖示例
- 帶有ListAdapter的 Android ListView示例
- Android SQLite 數據庫介紹
- Android SQLite 數據庫示例
- Android 動畫教程
- Android 中的通知
- Android 中的事件處理
- 如何在 Android 中發送帶有附件的電子郵件
- 雜項
- 選擇您的 JAVA IDE:Eclipse,NetBeans 和 IntelliJ IDEA
- Java S3 示例
- 如何在 Ubuntu 上為多個站點配置 Apache
- 如何在 Liferay DXP 中替代現成的(OOTB)模塊
- 簡單的 Git 教程
- 使用 Java 捕獲網絡數據包
- Selenium Java 教程
- 使用特定工作區運行 Eclipse
- 在 Eclipse 中安裝 SVN
- 如何運行 NodeJS 服務器
- SQL 內連接示例
- SQL 左連接示例
- SQL 右連接示例
- SQL 外連接示例
- 樹莓派
- Raspberry Pi 3 規格
- 將 Raspbian 安裝到 SD 卡
- Raspberry Pi 首次啟動
- 遠程連接到 Raspberry Pi
- 建立 Raspberry Pi 遠程桌面連接
- Raspberry Pi Java 教程
- 使用 PWM 的 Raspberry Pi LED 亮度調節
- Raspberry Pi 控制電機速度
- Raspberry Pi 用 Java 控制直流電機的速度和方向