dfs算法模板java

### DFS 算法的 Java 实现模板 以下是基于深度优先搜索（Depth First Search, DFS）算法的一个通用实现模板。此模板适用于图结构中的遍历问题。 #### 图表示方式 为了便于理解，这里采用邻接表的方式来存储图数据结构。通过 `ArrayList` 来模拟邻接表的形式[^1]。 ```java import java.util.*; public class Graph { private int V; // 顶点数量 private List<List<Integer>> adjList; public Graph(int vertices) { this.V = vertices; this.adjList = new ArrayList<>(vertices); for (int i = 0; i < vertices; ++i) { adjList.add(new ArrayList<>()); } } // 添加边到无向图中 public void addEdge(int u, int v) { adjList.get(u).add(v); // 对于有向图仅需这一句即可 adjList.get(v).add(u); // 如果是有向图，则不需要这句 } // 执行DFS的核心方法 public void DFSUtil(int vertex, boolean[] visited) { visited[vertex] = true; // 将当前节点标记为已访问 System.out.print(vertex + " "); // 访问该节点 Iterator<Integer> iterator = adjList.get(vertex).listIterator(); while (iterator.hasNext()) { // 遍历相邻节点 int adjacentVertex = iterator.next(); if (!visited[adjacentVertex]) { // 若未被访问过则继续递归调用 DFSUtil(adjacentVertex, visited); } } } // 主函数用于启动DFS过程 public void DFS() { boolean[] visited = new boolean[V]; // 初始化所有节点都未被访问的状态 Arrays.fill(visited, false); for (int i = 0; i < V; ++i) { // 处理可能存在的多个连通分量的情况 if (!visited[i]) { DFSUtil(i, visited); // 调用辅助函数执行实际的DFS逻辑 } } } public static void main(String args[]) { Graph g = new Graph(5); // 创建一个具有五个顶点的图实例 g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); System.out.println("Following is Depth First Traversal:"); g.DFS(); // 输出结果将是按DFS顺序排列的顶点序列 } } ``` 上述代码展示了如何构建一个简单的图类并实现了其上的DFS功能。它首先定义了一个基本的数据成员来保存图的信息以及一些必要的构造器和添加边的方法；接着提供了两个版本的DFS方法——一个是具体实现细节所在的内部工具方法 (`DFSUtil`) ，另一个则是负责初始化全局变量并向各个独立子图发起探索请求的主要入口(`DFS`) 。最后，在测试部分创建了一张小型样例网络并通过打印语句验证了预期行为[^3]。 对于拓扑排序而言，可以在此基础上稍作修改以适应特定需求[^2]。例如调整访问时机或者记录额外信息等策略均能有效支持更复杂的应用场景。