深度优先搜索（Depth-First Search，DFS）

深度优先搜索（Depth-First Search，DFS）介绍：

深度优先搜索（Depth-First Search，DFS）是一种图算法，用于遍历或搜索图的节点。它从起始节点开始，沿着一条路径尽可能深入地探索图，直到到达末端节点或无法继续前进，然后回溯到上一个节点，继续探索其他路径。

深度优先搜索（Depth-First Search，DFS）原理：

1. 选择一个起始节点，并将其标记为已访问。
2. 检查起始节点的邻居节点，选择一个未被访问的邻居节点。
3. 将选中的邻居节点标记为已访问，并将其加入遍历路径中。
4. 递归地应用步骤2和步骤3，直到当前节点没有未访问的邻居节点。
5. 回溯到上一个节点，并继续检查其他未访问的邻居节点。
6. 重复步骤2到步骤5，直到遍历完整个图或找到目标节点。

Java 代码实现：

DFS使用栈或递归来实现。使用栈时，可以将待访问的节点依次入栈，并在遍历过程中不断出栈节点进行处理。使用递归时，递归函数会自动处理节点的遍历顺序和回溯。

package com.algorithm.graph;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class DFS {/*** 测试方法** @param args*/public static void main(String[] args) {/*** 构建一个二叉树，调用 DFS 算法*/Graph graph = new Graph(6);graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(2, 5);System.out.println("Depth-First Traversal (starting from vertex 0):");graph.DFS(0);}
}/*** 图数据结构*/
class Graph {/*** 节点数量*/private int numVertices;/*** 邻接表*/private List<List<Integer>> adjacencyList;/*** 构造方法** @param numVertices 节点数量*/public Graph(int numVertices) {this.numVertices = numVertices;this.adjacencyList = new ArrayList<>(numVertices);for (int i = 0; i < numVertices; i++) {adjacencyList.add(new ArrayList<>());}}/*** 添加边到邻接表** @param source      起点* @param destination 终点*/public void addEdge(int source, int destination) {adjacencyList.get(source).add(destination);}/*** 深度优先搜索算法实现** @param startVertex 进行 DFS 的顶点*/public void DFS(int startVertex) {/*** 标记节点是否已被访问*/boolean[] visited = new boolean[numVertices];/*** 存储待访问的节点*/Stack<Integer> stack = new Stack<>();/*** 将第一个节点（头节点）标记为已访问*/visited[startVertex] = true;/*** 将第一个节点入栈*/stack.push(startVertex);/*** 遍历整个栈*/while (!stack.isEmpty()) {/*** 获取当前栈顶元素（节点）*/int currentVertex = stack.pop();/*** 打印当前节点*/System.out.print(currentVertex + " ");List<Integer> neighbors = adjacencyList.get(currentVertex);/*** 遍历所有邻接点，如果节点没有访问过，则访问并入栈*/for (int neighbor : neighbors) {if (!visited[neighbor]) {visited[neighbor] = true;stack.push(neighbor);}}}}
}

代码简单解释：

该代码中，首先定义了一个Graph类表示图数据结构，其中包括节点数量numVertices和邻接表adjacencyList。addEdge方法用于添加边到邻接表。

在DFS方法中，使用一个布尔数组visited来标记节点是否已被访问。创建一个栈stack用于存储待访问的节点。首先将起始节点标记为已访问并入栈。接下来，从栈中取出节点，打印该节点，并将其未访问的邻居节点标记为已访问并入栈。重复这个过程直到栈为空。

在主函数中，创建一个Graph对象，并通过addEdge方法添加边。然后调用DFS方法以深度优先的方式遍历图，从起始节点0开始。

程序执行结果：

Depth-First Traversal (starting from vertex 0):
0 2 5 4 1 3 
Process finished with exit code 0

DFS的应用：

1. 图的遍历：DFS可以用于遍历图中的所有节点，以便获取图的结构信息或执行特定操作。
2. 连通性检测：DFS可以用于检测图中的连通分量，即查找图中的所有连通子图。
3. 拓扑排序：DFS可以进行拓扑排序，即对有向无环图进行排序，使得任何有向边的起始节点都排在终止节点的前面。
4. 寻找路径：DFS可以用于寻找两个节点之间的路径，如迷宫问题、远程路径规划等。
5. 回溯算法：DFS的回溯特性使其成为解决组合优化问题、生成排列和组合等问题的有效方法。

需要注意的是，DFS没有保证找到最优解，它只能保证找到可行解。对于某些问题，如最短路径问题，通常需要使用其他算法（如Dijkstra算法）来获得最优解。

用图画的方式描述 DFS 算法:

当我们使用图来描述DFS算法时，可以通过节点和边的连接关系来表示图的结构。下面是一个使用节点和边的图示例，描述DFS算法的执行过程：

假设我们有以下图结构：

     0/ \1   2/   / \3   4   5

开始时，选择起始节点0进行深度优先搜索。我们从节点0开始，然后沿着一条路径尽可能深入地探索。
首先，我们选择节点1作为下一个要探索的节点，然后再选择节点3。
由于节点3没有未访问的邻居节点，我们回溯到节点1。
接下来，我们选择节点2作为下一个要探索的节点，然后再选择节点4。
再次回溯到节点2，我们发现节点2还有一个未访问的邻居节点5。
因此，我们选择节点5进行探索。

DFS算法执行的过程描述：

1. 选择起始节点0，并将其标记为已访问。

     0*/ \1   2/   / \3   4   5

2. 选择节点0的邻居节点1，并将其标记为已访问。

     0*/ \1*  2/   / \3   4   5

3. 选择节点1的邻居节点3，并将其标记为已访问。

     0*/ \1*  2/   / \3*  4   5

4. 回溯到节点1，因为节点1没有其他未访问的邻居节点。

5. 选择节点2的邻居节点4，并将其标记为已访问。

     0*/ \1   2*/   / \3   4*  5

6. 回溯到节点2。

7. 选择节点2的邻居节点5，并将其标记为已访问。

     0*/ \1   2*/   / \3   4   5*

8. 回溯到节点2，因为节点2没有其他未访问的邻居节点。

9. 回溯到节点0。

最终，DFS算法的遍历路径为0-1-3-2-4-5。

通过图的可视化，可以更直观地理解DFS算法的执行过程，以及节点的访问顺序和回溯操作。