DFSBFS总结

DFS（深度优先搜索）算法适用于解决以下问题：

图遍历：DFS可以用来遍历图，找到所有节点或者遍历到目标节点；
连通性问题：DFS可以用来判断两个节点之间是否存在路径，比如在迷宫中找出一条从起点到终点的路径；
拓扑排序：DFS可以用来进行拓扑排序，将有依赖关系的任务按照顺序执行；
寻找连通块：DFS可以用来寻找无向图中的连通块，也可以用来找到有向图中的强连通分量；
生成Maze：使用DFS可以生成迷宫。
总之，DFS是一种非常常用的搜索算法，它在很多问题上都有着广泛的应用。

以下是一个简单的Java DFS模板，可以用来解决各种DFS问题：

import java.util.*;public class DFS {// 定义visited数组，用来标记节点是否被访问过private boolean[] visited;// 定义邻接矩阵graph，表示图的连接关系private int[][] graph;// 定义节点个数和起始节点startprivate int n, start;public void dfs() {visited = new boolean[n];dfs(start);}private void dfs(int i) {// 标记当前节点为已访问visited[i] = true;System.out.print(i + " ");for (int j = 0; j < n; j++) {if (graph[i][j] == 1 && !visited[j]) {// 如果i和j之间有连接，并且j还没有被访问过，则递归访问jdfs(j);}}       }public static void main(String[] args) {DFS g = new DFS();g.n = 5;g.start = 0;g.graph = new int[][]{{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{0, 1, 0, 0, 1},{1, 1, 0, 0, 1},{0, 1, 1, 1, 0}};g.dfs();}
}

在这个例子中，我们定义了一个DFS类，其中包含了dfs()和dfs(int i)两个方法。在dfs()方法中，我们初始化visited数组，并从起始节点开始访问；在dfs(int i)方法中，我们首先标记当前节点为已访问，并输出它的编号，然后遍历与它相连的所有节点，如果这些节点还没有被访问过，则递归访问它们。

在main方法中，我们创建了一个DFS对象，并定义了一个5个节点的图，其中每个元素表示节点之间的连接关系。最后调用dfs()方法，即可完成DFS遍历。

Java BFS（广度优先搜索）是一种经典的图遍历算法，用于解决各种与图相关的问题，例如：

1. 无权图最短路径问题：在一个无权图中，求从起点到目标点的最短路径。

2. 连通性问题：判断一个无向图是否连通，或者有几个连通分量。

3. 双向BFS问题：s到t的最短路。提供了两个数据结构begQueue和endQueue，以及两个变量begVisited,endVisited。算法执行时每次从大小较小的那一端去继续进行。

4. 零钱兑换问题：给定不同面额的硬币coins和一个总金额amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

5. 二叉树层序遍历问题：打印出一棵二叉树的所有节点值，按照从上到下、从左到右的顺序。 

等等。

因此，Java BFS是解决许多实际问题时常用的算法之一。

以下是一个简单的Java BFS模板，可以用来解决各种BFS问题：

import java.util.*;public class BFS {// 定义visited数组，用来标记节点是否被访问过private boolean[] visited;// 定义邻接矩阵graph，表示图的连接关系private int[][] graph;// 定义节点个数和起始节点startprivate int n, start;public void bfs() {Queue<Integer> queue = new LinkedList<>();queue.offer(start);visited[start] = true;while (!queue.isEmpty()) {int cur = queue.poll();System.out.print(cur + " ");for (int i = 0; i < n; i++) {if (graph[cur][i] == 1 && !visited[i]) {visited[i] = true;queue.offer(i);}}}}public static void main(String[] args) {BFS g = new BFS();g.n = 5;g.start = 0;g.graph = new int[][]{{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{0, 1, 0, 0, 1},{1, 1, 0, 0, 1},{0, 1, 1, 1, 0}};g.visited = new boolean[g.n];g.bfs();}
}

在这个例子中，我们定义了一个BFS类，其中包含了bfs()方法。在bfs()方法中，我们首先创建一个队列，并将起始节点加入队列中，然后标记起始节点为已访问。接着，我们循环处理队列中的节点，对于每个节点，我们输出它的编号，并把与它相连的所有未访问过的节点加入到队列中。最后输出结果即可。

在main方法中，我们创建了一个BFS对象，并定义了一个5个节点的图，其中每个元素表示节点之间的连接关系。我们还初始化了visited数组，并调用bfs()方法来完成BFS遍历。