数据结构-深度优先搜索Java实现

一、引言

    深度优先搜索（DFS）是一种在图或树中进行搜索的算法，它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都已探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
    DFS是一种盲目搜索，即它并不需要知道目标的位置，只是尽可能地遍历所有可能的路径。因此，它的搜索效率并不高，特别是在面对大规模数据时。然而，DFS可以找到目标值或解决目标问题，对于解决NP问题作用很大。
    此外，DFS如同数据结构中的栈结构，是一种后进先出的结构，导致了所有的点进入栈时有一个顺序，我们称之为 “DFS序”。

二、算法步骤

深度优先搜索算法的步骤如下：

1. 选取图中某一顶点Vi为出发点，访问并标记该顶点。
2. 以Vi为当前顶点，依次搜索Vi的每个邻接点Vj，若Vj未被访问过，则访问和标记邻接点Vj，若Vj已被访问过，则搜索Vi的下一个邻接点。
3. 以Vj为当前顶点，重复步骤2），直到图中和Vi有路径相通的顶点都被访问为止。
4. 若图中尚有顶点未被访问过（非连通的情况下），则可任取图中的一个未被访问的顶点作为出发点，重复上述过程，直至图中所有顶点都被访问。

三、原理演示

递归实现

1. 选择起始节点：从图中的一个起始节点开始，将该节点标记为已访问。
2. 递归探索邻居节点：对于当前节点，遍历它的邻居节点。如果邻居节点尚未被访问，就递归地调用深度优先搜索函数，以此邻居节点为新的起始节点，重复步骤1。
3. 回溯：当当前节点的所有邻居节点都被访问后，回溯到上一个节点，并继续遍历其未被访问的邻居节点。
4. 重复步骤2和3，直到图中的所有节点都被访问。

下面是递归实现深度优先搜索的示例代码：

public void dfsRecursive(Node node, Set<Node> visited) {
   visited.add(node);
   System.out.print(node.value + " ");
   
   for (Node neighbor : node.neighbors) {
       if (!visited.contains(neighbor)) {
           dfsRecursive(neighbor, visited);
       }
   }
}
1
2
3
4
5
6
7
8
9
10

非递归实现（使用堆栈）

1. 选择起始节点：从图中的一个起始节点开始，将该节点标记为已访问，并将它入栈。
2. 迭代遍历：使用一个循环，不断从栈中弹出节点，然后遍历它的邻居节点。
3. 探索邻居节点：对于当前弹出的节点，遍历其邻居节点。如果邻居节点尚未被访问，就将其标记为已访问并将其入栈。
4. 重复步骤2和3，直到栈为空。

下面是非递归实现深度优先搜索的示例代码：

public void dfsIterative(Node start) {
   Stack<Node> stack = new Stack<>();
   Set<Node> visited = new HashSet<>();

   stack.push(start);
   visited.add(start);

   while (!stack.isEmpty()) {
       Node current = stack.pop();
       System.out.print(current.value + " ");
       
      for (Node neighbor : current.neighbors) {
          if (!visited.contains(neighbor)) {
               stack.push(neighbor);
               visited.add(neighbor);
           }
       }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

无论采用递归还是非递归方式，深度优先搜索的关键思想是深入到尽可能深的层级，直到无法再深入为止，然后回溯到上一个节点，继续探索。这一过程不断重复，直到遍历整个图。深度优先搜索对于解决路径查找、拓扑排序、连通性检测等问题都非常有用。

四、代码实战

以下是深度优先搜索算法的Java代码实现：

import java.util.*;

public class DFS {
   private int V; // 顶点数量
   private LinkedList<Integer> adj[]; // 邻接表

   // 构造函数
   DFS(int v) {
       V = v;
       adj = new LinkedList[v];
       for (int i = 0; i < v; ++i) {
           adj[i] = new LinkedList();
       }
   }

   // 添加边
   void addEdge(int v, int w) {
       adj[v].add(w);
   }

   // DFS函数
   void DFSUtil(int v, boolean visited[]) {
       // 标记当前节点为已访问并输出该节点
       visited[v] = true;
       System.out.print(v + " ");

       // 递归访问与v节点相邻的未访问节点
       Iterator<Integer> i = adj[v].listIterator();
       while (i.hasNext()) {
           int n = i.next();
           if (!visited[n])
               DFSUtil(n, visited);
       }
   }

   // DFS函数
   void DFS(int v) {
       // 标记所有顶点为未访问状态
      boolean visited[] = new boolean[V];

       // 调用递归函数DFSUtil开始从顶点v进行DFS遍历
       DFSUtil(v, visited);
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

五、结论

我们一起来总结一下：
深度优先搜索在计算机科学中有着广泛的应用，例如用于遍历树或图的结构、查找路径、解决优化问题等。它的优点在于空间复杂度相对较小，可以处理大规模的数据，同时可以避免搜索冗余的节点。然而，深度优先搜索也有其局限性，例如可能会陷入死循环或无法找到最优解，因此需要根据具体问题选择合适的算法进行优化。
点赞收藏，富婆包养✋✋