深度優先搜尋DFS即Depth First Search。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。廣度優先搜尋BFS是Breadth First Search。所有因為展開節點而得到的子節點都會被加進一個先進先出的佇列。
DFS/BFS搜尋演算法分析
#定理一：深度優先搜尋標記與起點連通的所有頂點所需的時間和頂點的度數總和成正比。
假設我們有兩個點v和w，在一張圖中，當v先訪問到w時，v-w這條邊從未檢查的狀態變成已檢查，此時這條邊訪問了一次。當w訪問v時，w-v這邊又被檢查一次，但是發現已經被檢查，此時這條邊被訪問了兩次。除此之外，不可能再有其他情況導致v-w（w-v）這條邊被訪問。所以可得，圖中每條邊會被訪問兩次，邊×2 = 頂點 Σ 度數 （各頂點度數之和）。所以成正比。
定理二：一般的，使用深度優先搜尋能解決的問題都可轉換為廣度優先搜尋解決。
深度優先搜尋的優點在於：遞迴易於理解、簡單。但是深度優先搜索並沒有明確的目的性，而廣度優先搜索按照由近及遠的順序搜索，在很多情況下能找出最優解，而且循環的效率高於遞歸，並沒有棧溢位的風險。在稀疏圖中廣度優先搜尋的效率更是快過深度優先搜尋很多，稠密圖相差無幾。在不一定需要廣度優先搜尋的情況下，我們可以盡量使用深度優先搜尋。
定理三：使用鄰接表作為圖記錄方法時，深度優先搜尋與廣度優先搜尋時間複雜度均為O(V+E)。
存取元素所需的時間主要取決於圖資料的記錄方法，無論是深度優先搜索或是廣度優先搜索，都需要檢查整張圖後才能計算完畢，耗時的主要部分取決於記錄方式，在使用鄰接矩陣作為記錄數據的方法時，複雜度為O(n2)，而鄰接表中只有(頂點+邊數×2)的數據，我們只需要執行其中一半的邊數，另一半可由檢查免除運算。所以，使用鄰接表作為圖記錄方法時，DFS與BFS時間複雜度均為O(V+E)。
基本資料結構－圖類
深度優先演算法和廣度優先演算法是基於圖論的演算法。在實作應用之前，先實作基本的無向圖類別資料結構。
Graph類別用V定義定點，E定義邊，LinkedListInteger>[ ]定義鄰接表。
package Graph;
import java.util.LinkedList;
public class Graph {
private final int V;
private int E;
private LinkedList<Integer>[] adj;
public Graph(int V) {
this.V = V;
this.E = 0;
adj = (LinkedList<Integer>[]) new LinkedList[V];
for (int v = 0; v < V; v++)
adj[v] = new LinkedList<>();
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public LinkedList<Integer> adj(int v) {
return adj[v];
}
public int degree(int v,Graph g){
int count = 0;
for(int s : adj(v))
count++;
return count;
}
}Graph類別中的泛型陣列
#需要說明的是：這裡雖然只是宣告了泛型陣列、用普通陣列類型轉化來實現，但也存在安全隱患。
類似下面的程序，編譯通過但是內容出錯，因為泛型在運行期被擦除，Object數組類間進行賦值不報錯。
public static void main(String[] args) {
LinkedList<Integer>[] adj;
adj = (LinkedList<Integer>[]) new LinkedList[5];
Object o = adj;
Object[] oa = (Object[]) o;
List<String> li = new LinkedList<>();
li.add("s");
oa[0] = li;
System.out.println(adj[0]);
}這種情況需要了解，但這篇文章主要介紹演算法，這部分不過多討論。謹在此列出出錯的可能性。
連線問題
package Graph;
import java.util.ArrayDeque;
import java.util.Queue;
public class Connected {
private Graph g;
private boolean[] marked;
private int count;
public Connected(Graph g) {
this.g = g;
marked = new boolean[g.V()];
}
/**
* DFS算法计算连通结点
*
* @param s
* 起点
*/
public void DFS(int s) {
marked[s] = true;
count++;
for (int w : g.adj(s))
if (!marked[w])
DFS(w);
}
/**
* BFS算法计算连通结点
*
* @param s
* 起点
*/
public void BFS(int s) {
Queue<Integer> q = new ArrayDeque<>();
q.add(s);
marked[s] = true;
count++;
while (!q.isEmpty()) {
for (int w : g.adj(q.poll()))
if (!marked[w]) {
marked[w] = true;
count++;
q.add(w);
}
}
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 返回该起点总连通结点数
*
* @return 连通结点数
*/
public int count() {
return count;
}
/**
* 判断一个结点是否被连通
*
* @param v
* 判断结点
* @return 连通状态
*/
public boolean isMarked(int v) {
return marked[v];
}
}單點路徑存在問題
package Graph;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
public class Paths {
private Graph g;
private boolean[] marked;
private int[] edgeTo;
public Paths(Graph g) {
this.g = g;
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
}
/**
* DFS算法计算单点路径问题
*
* @param s
* 起点
*/
public void DFS(int s) {
marked[s] = true;
for (int w : g.adj(s))
if (!marked[w]) {
edgeTo[w] = s;
DFS(w);
}
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 判断一个结点是否被连通
*
* @param v
* 判断结点
* @return 连通状态
*/
public boolean isMarked(int v) {
return marked[v];
}
/**
* 是否存在从s到v的路径，默认调用深度优先，可以选择广度优先
*
* @param s
* 起点
* @param v
* 终点
* @return 存在状态
*/
public boolean hasPathTo(int s, int v) {
DFS(s);
if (isMarked(v))
return true;
return false;
}
}單點最短路徑
package Graph;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
public class Paths {
private Graph g;
private boolean[] marked;
private int[] edgeTo;
public Paths(Graph g) {
this.g = g;
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
}
/**
* DFS算法计算单点路径问题
*
* @param s
* 起点
*/
public void DFS(int s) {
marked[s] = true;
for (int w : g.adj(s))
if (!marked[w]) {
edgeTo[w] = s;
DFS(w);
}
}
/**
* BFS算法计算单点最短路径问题
*
* @param s
* 起点
*/
public void BFS(int s) {
Queue<Integer> q = new ArrayDeque<>();
q.add(s);
marked[s] = true;
while (!q.isEmpty()) {
for (int w : g.adj(q.poll()))
if (!marked[w]) {
marked[w] = true;
edgeTo[w] = s;
q.add(w);
}
}
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 判断一个结点是否被连通
*
* @param v
* 判断结点
* @return 连通状态
*/
public boolean isMarked(int v) {
return marked[v];
}
/**
* 是否存在从s到v的路径，默认调用深度优先，可以选择广度优先
*
* @param s
* 起点
* @param v
* 终点
* @return 存在状态
*/
public boolean hasPathTo(int s, int v) {
DFS(s);
// BFS(v);
if (isMarked(v))
return true;
return false;
}
/**
* 输出最短路径
*
* @param s
* 起点
* @param v
* 终点
*/
public void pathTo(int s, int v) {
if (!hasPathTo(s, v))
return;
BFS(s);
// DFS(s); 但深度优先可能不是最短路径
Stack<Integer> sta = new Stack<>();
sta.push(v);
for (int i = v; i != s; i = edgeTo[i])
sta.push(edgeTo[i]);
while (!sta.isEmpty())
System.out.println(sta.pop() + " ");
}
}連通分量計算
package Graph;
public class ConnectedComp {
private Graph g;
private boolean[] marked;
private int count;
private int[] id;
public ConnectedComp(Graph g) {
this.g = g;
id = new int[g.V()];
marked = new boolean[g.V()];
}
/**
* 调用方法，便利全部结点判断分量数
*/
public void DFS() {
for (int s = 0; s < g.V(); s++) {
if (!marked[s]) {
DFS(s);
count++;
}
}
}
/**
* DFS算法计算连通结点
*
* @param s
* 起点
*/
private void DFS(int s) {
marked[s] = true;
id[s] = count;
for (int w : g.adj(s))
if (!marked[w])
DFS(w);
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 返回该图总分量数目
*
* @return 分量数
*/
public int count() {
return count;
}
/**
* 返回该节点属于第几个分量
*
* @param s
* 判断结点
* @return 分量组数
*/
public int id(int s) {
return id[s];
}
}無環圖問題
package Graph;
public class Cycle {
private Graph g;
private boolean[] marked;
private boolean hasCycle;
public Cycle(Graph g) {
this.g = g;
marked = new boolean[g.V()];
for(int s=0;s<g.V();s++)
if(!marked[s])
DFS(s,s);
}
/**
* DFS算法计算无环图问题
*
* @param s
* 起点
*/
public void DFS(int s, int v) {
marked[s] = true;
for (int w : g.adj(s))
if (!marked[w])
DFS(w, s);
else if (w != v)
hasCycle = true;
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 判断是否有环
*
* @return 判断结果
*/
public boolean hasCycle() {
return hasCycle;
}
}二分圖雙色問題
package Graph;
public class TwoColor {
private Graph g;
private boolean[] color;
private boolean[] marked;
private boolean isTwoColor;
public TwoColor(Graph g) {
this.g = g;
marked = new boolean[g.V()];
color = new boolean[g.V()];
isTwoColor = true;
for(int s=0;s<g.V();s++)
if(!marked[s])
DFS(s);
}
/**
* DFS算法计算二分图问题
*
* @param s
* 起点
*/
public void DFS(int s) {
marked[s] = true;
for (int w : g.adj(s))
if (!marked[w]) {
color[w] = !color[s];
DFS(w);
} else if (color[w] == color[s])
isTwoColor = false;
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 判断是否为二分图
*
* @return 判断结果
*/
public boolean isTwoColor() {
return isTwoColor;
}
}以上是java優先搜尋（DFS/BFS）實際應用的詳細內容。更多資訊請關注PHP中文網其他相關文章！
如何將Maven或Gradle用於高級Java項目管理，構建自動化和依賴性解決方案？Mar 17, 2025 pm 05:46 PM本文討論了使用Maven和Gradle進行Java項目管理，構建自動化和依賴性解決方案，以比較其方法和優化策略。
如何使用適當的版本控制和依賴項管理創建和使用自定義Java庫（JAR文件）？Mar 17, 2025 pm 05:45 PM本文使用Maven和Gradle之類的工具討論了具有適當的版本控制和依賴關係管理的自定義Java庫（JAR文件）的創建和使用。
如何使用咖啡因或Guava Cache等庫在Java應用程序中實現多層緩存？Mar 17, 2025 pm 05:44 PM本文討論了使用咖啡因和Guava緩存在Java中實施多層緩存以提高應用程序性能。它涵蓋設置，集成和績效優勢，以及配置和驅逐政策管理最佳PRA
如何將JPA（Java持久性API）用於具有高級功能（例如緩存和懶惰加載）的對象相關映射？Mar 17, 2025 pm 05:43 PM本文討論了使用JPA進行對象相關映射，並具有高級功能，例如緩存和懶惰加載。它涵蓋了設置，實體映射和優化性能的最佳實踐，同時突出潛在的陷阱。[159個字符]
Java的類負載機制如何起作用，包括不同的類載荷及其委託模型？Mar 17, 2025 pm 05:35 PMJava的類上載涉及使用帶有引導，擴展程序和應用程序類負載器的分層系統加載，鏈接和初始化類。父代授權模型確保首先加載核心類別，從而影響自定義類LOA
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
AI Hentai Generator
免費產生 AI 無盡。
熱門文章
熱工具
EditPlus 中文破解版
體積小，語法高亮，不支援程式碼提示功能
記事本++7.3.1
好用且免費的程式碼編輯器
SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合，這些清單在安全評估過程中經常使用，而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表，幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上，他就可以存取所需的每種類型的清單。
MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中，你可以繼續在那裡關注我們。 MinGW：GNU編譯器集合（GCC）的本機Windows移植版本，可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔；包括對MSVC執行時間的擴展，以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。
ZendStudio 13.5.1 Mac
強大的PHP整合開發環境
