Java中的DFS演算法-java教程-PHP中文網

Java中的DFS演算法

王林

發布： 2024-08-30 15:30:19

原創

1079 人瀏覽過

DFS演算法是一種遍歷演算法，被定義為一種搜尋演算法，簡稱為深度優先搜索，也稱為圖演算法，因為它在看起來像圖結構的樹結構中進行搜索，因此它從根並沿著下圖以不同的分支進行遍歷。一般來說，Java中的DFS演算法被定義為一種遍歷樹或圖結構的遍歷演算法，從初始點的根節點開始，深入每個分支，直到到達已知的任何最後一個分支的最後一個節點。作為深度優先搜索，這提供了 3 種不同的 DFS 方式，例如前序、中序和後序遍歷搜索。

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

演算法：

DFS 是一種統一演算法，會產生非最優解，DFS 演算法的工作原理如下：

第 1 步： 從任何給定圖或樹的根節點開始。

第 2 步： 現在將根節點視為圖的第一個節點，並將該節點放置在堆疊或列表的頂部。

第 3 步： 現在尋找根節點（即第一個節點）的相鄰節點，並將這些相鄰節點新增至另一個相鄰節點清單。

第四步：然後繼續加入根節點之後的堆疊或清單中每個節點的相鄰節點。

第 5 步： 繼續第 3 步到第 4 步，直到到達圖中最後一個分支的結束節點或相鄰節點清單變空。

因此，Java中的DFS演算法是從初始節點深度搜尋直到結束節點的遍歷搜尋演算法之一。然而，有時在遍歷圖時會感到困惑，無論是透過左分支還是右分支；為了解決這個問題，DFS 提供了3 種不同類型的前序、中序和後序，用於根據指定的順序遍歷樹。

DFS 演算法如何與範例配合使用？

在Java中，DFS演算法根據上述演算法工作。非有向圖的DFS演算法將從根節點開始，首先將該根節點放入一個堆疊中，該堆疊可以視為保存已存取節點的已存取堆疊，然後將根節點的所有相鄰節點放入該堆疊中。訪問了根節點所在的堆疊。然後遍歷圖，然後找到每個根的相鄰節點的相鄰節點，繼續直到圖的最後一個節點，透過將所有節點放入另一個堆疊中來遍歷這些節點，完成搜尋後，顯示訪問過的堆疊，給出已遍歷圖形的節點。

範例#1

現在讓我們來看一個簡單的 DFS 演算法範例，它是用 Java 程式語言在斷開連接的圖上實現的。

代碼：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class vertex
{
int root, dest;
public vertex(int root, int dest)
{
this.root = root;
this.dest = dest;
}
}
class graphstruc
{
List<List<Integer>> adjList = null;
graphstruc(List<vertex> v, int N)
{
adjList = new ArrayList<>();
for (int i = 0; i < N; i++) {
adjList.add(new ArrayList<>());
}
for (vertex e: v)
{
int src = e.root;
int dest = e.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
class Main
{
public static void DFS(graphstruc graph, int v, boolean[] d)
{
d[v] = true;
System.out.print(v + " ");
for (int u: graph.adjList.get(v))
{
if (!d[u]) {
DFS(graph, u, d);
}
}
}
public static void main(String[] args)
{
List<vertex> v = Arrays.asList(
new vertex(1, 2), new vertex(1, 7), new vertex(1, 8),
new vertex(2, 3), new vertex(2, 6), new vertex(3, 4),
new vertex(3, 5), new vertex(8, 9), new vertex(8, 12),
new vertex(9, 10), new vertex(9, 11), new vertex(10, 12),
new vertex(10, 13), new vertex(11, 14)
);
final int N = 15;
graphstruc g = new graphstruc(v, N);
boolean[] d = new boolean[N];
System.out.println("Demonstration of Depth First Search algorithm in Java is as follows:");
for (int i = 0; i < N; i++)
{
if (!d[i]) {
DFS(g, i, d);
}
}
}
}

登入後複製

輸出：

Java中的DFS演算法

在上面的範例中，我們首先定義一個類別頂點，我們將在其中聲明圖中的根頂點和目標頂點，該類別頂點儲存圖的頂點。然後我們定義類別graphstruc來聲明根節點的相鄰頂點並將這些相鄰節點新增到清單中。我們儲存相鄰頂點，然後將這些頂點的相鄰頂點新增到清單中。然後，為了執行 DFS，我們聲明一個 DFS 類，透過它我們將從給定圖中識別當前節點，然後繼續識別每個節點的相鄰節點並新增相鄰清單節點。最後，在主類別中，我們將圖頂點列表定義為數組以及節點總數，在呼叫 DFS 函數後，它將在 DFS 搜尋列表中顯示該列表，如上面的螢幕截圖所示，這是輸出。

範例#2

現在讓我們來看看 Java 中前序、中序和後序遍歷等不同型別遍歷順序的 DFS 實作。下面我們將看到 Java 中的預購實作。

代碼：

class vertex
{
int data;
vertex l, r;
public vertex(int k)
{
data = k;
l = r = null;
}
}
class Main
{
public static void preorder(vertex root)
{
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.l);
preorder(root.r);
}
public static void main(String[] args)
{
vertex root = new vertex(2);
root.l = new vertex(3);
root.r = new vertex(1);
root.l.l = new vertex(6);
root.r.l = new vertex(4);
root.r.r = new vertex(5);
root.r.l.l = new vertex(8);
root.r.l.r = new vertex(7);
preorder(root);
}
}

登入後複製

輸出：

Java中的DFS演算法