DFS

深度优先搜索的基本思路就是从一个节点开始，一只遍历其可以到达的节点，直到遍历的节点没有任何可以达到且没有遍历到的节点，此时返回上一个节点，继续遍历上一个节点的可到达且尚未遍历的节点，直到所有相连的节点都被访问到了。

Code

递归的DFS比较好理解：

public void DFS(char[][] board, char[] chs, int x, int y, boolean[][] visited) {
// 控制边界
if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) return false;
// 如果已经遍历过了，那么就不用在遍历了
if (visited[x][y]) {
return false;
}
// 修改变量
visited[x][y] = true;
// 下面可以写你的处理逻辑
....
// 搜索四个方向
DFS(board, chs, idx+1, x-1, y, visited);
DFS(board, chs, idx+1, x+1, y, visited);
DFS(board, chs, idx+1, x, y-1, visited);
DFS(board, chs, idx+1, x, y+1, visited);
// 回溯的逻辑 比如 visited[x][y] = false;
...
return res;
}

使用建议

1. 首先DFS是一种很灵活算法，其难点不在于写代码的本身，而在于如何将问题转化成DFS的求解方式；
2. 上述模板只是从一个起点开始的DFS搜索，如果想全部搜索则从每个位置开始即可；
3. 设计DFS算法的时候需要考虑：
   1. DFS的参数（基本参数+问题中需要用到的参数）；
   2. DFS递归的结束条件（基本条件+问题中涉及的条件）；
   3. DFS的返回值的考虑；
   4. DFS结束后是否需要进行回溯（比如还原状态变量）。

BFS

广度优先搜索也是一样，只不过是从一个节点出发，访问其所有的可到达的节点，然后从其可到达的节点中再选择一个节点进行访问，直到所有节点都被访问。

Code

public int orangesRotting(int[][] grid) {
if (grid.length == 0) {
return 0;
}
Deque<int[]> queue = new ArrayDeque();
// 建立初始状态
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (满足条件) {
queue.offer(new int[] {i,j});
}
}
}
// 开始BFS
int[] dx = new int[] {-1, 1, 0, 0}, dy = new int[] {0, 0, -1, 1};
while (!queue.isEmpty()) {
int[] point = queue.poll();
int x = point[0], y = point[1];
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newX < m && newY >= 0 && newY < n
&& 问题的条件) {
// 下标入队列
queue.offer(new int[] {newX, newY});
// 你的处理逻辑
}
}
}
}

使用建议

1. BFS可以是看做从一个个点不断向外扩散的过程；
2. 使用BFS通常可以解决最短、最长路径问题，因为BFS每轮遍历可以计数，而DFS的遍历统计起来比较麻烦。

最后

以上就是任性招牌为你收集整理的算法模板——DFS和BFSDFSBFS的全部内容，希望文章能够帮你解决算法模板——DFS和BFSDFSBFS所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。