Java中的DFS算法

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);
}
}
}
}

输出：

在上面的示例中，我们首先定义一个类顶点，我们将在其中声明图中的根顶点和目标顶点，该类顶点存储图的顶点。然后我们定义类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);
}
}

输出：

上面的例子也与前面的例子类似，唯一的区别是我们在 DFS 算法中定义遍历顺序。在此，我们仅定义前序遍历顺序，定义后它将按根节点、左节点和右节点的顺序遍历深度优先图。因此，在这里，我们将节点 2 声明为根节点，将节点 3 声明为左节点，将节点 6 声明为右节点，依此类推。输出如上图所示。

结论

本文的结论是，Java中的DFS算法是一种遍历算法，用于对图进行深度查找或搜索，直到访问到最后一个节点。 DFS 算法的时间复杂度通常用 O(E+V) 表示，其中 E 表示图的边，V 表示图的顶点。根据遍历顺序，DFS 算法有许多不同的应用，可分为中序、前序和后序 DFS 遍历图。

以上是Java中的DFS算法的详细内容。更多信息请关注PHP中文网其他相关文章！