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;
// 定义节点个数和起始节点start
private 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还没有被访问过，则递归访问j
dfs(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;
// 定义节点个数和起始节点start
private 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遍历。