Java实现dfs和bfs算法

### Java 实现 DFS 和 BFS 算法 #### 深度优先搜索（DFS） 深度优先搜索通过尽可能深入地访问节点来遍历或搜索树或图的数据结构。当遇到未访问过的顶点时，该方法会立即对其进行处理并继续向更深层次前进直到无法再深入为止。 ```java import java.util.*; public class Graph { private int V; private LinkedList<Integer> adj[]; @SuppressWarnings("unchecked") Graph(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); } void DFSUtil(int v, boolean visited[]) { visited[v] = true; System.out.print(v + " "); Iterator<Integer> i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) DFSUtil(n, visited); } } void DFS(int v) { boolean visited[] = new boolean[V]; DFSUtil(v, visited); } } ``` 此代码展示了如何创建一个简单的无向图，并执行从给定起点开始的深度优先搜索[^3]。 #### 广度优先搜索（BFS） 广度优先搜索按照层次顺序逐层展开搜索过程，在同一层内按从左到右的方式依次选取下一个要扩展的状态进行考察。对于每一个被选中的状态，先将其所有子结点加入队列等待后续处理；然后再从未访问过这些新产生的子结点中挑选出最早进入队列的一个作为当前待处理对象重复上述操作直至找到目标解或者全部候选都已穷尽。 ```java void BFS(int s) { boolean visited[] = new boolean[V]; LinkedList<Integer> queue = new LinkedList<Integer>(); visited[s] = true; queue.add(s); while (queue.size() != 0) { s = queue.poll(); System.out.print(s + " "); Iterator<Integer> i = adj[s].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) { visited[n] = true; queue.add(n); } } } } ``` 这段程序实现了基于队列机制的广度优先遍历功能，能够有效地对连通分量内的各个顶点实施系统化的扫描工作[^5]。