干货！图解DFS&BFS算法以及模板以及例题_dfs bfs ucs相关题目

本篇文章结合了网上几位大佬的文章阐述了DFS和BFS的算法原理和相关例题，如有错误请大家不吝赐教

参考以下链接学习DFS和BFS的算法原理：

图解DFS&BFS

---

对比：
DFS 算法
思想： 一直往深处走，直到找到解或者走不下去为止；通常用递归或者栈（保存未被遍历的结点，结点按照深度优先的次序被访问并依次被压入栈中）来实现；反复进行直到所有节点都被访问为止。
例子： 走迷宫（不走到死胡同不回头，直到找到出口）
基本模板:

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}

void dfs(int step)
{
        标记
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件//可以是判断该元素有没有被访问过
               //也可以在这里做标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）//!!!回溯的时候很重要
        }
}   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

BFS算法
思想： 一圈一圈往外找；通常用队列来实现
找到的是最短的路径。（这个很重要，bfs第一次找到的到达目标的路径就是最短路径！）
例子： 趴在地板上找眼镜，总是先找最近的地方，如果没有再往远处找

---

示例代码：
参考链接
一、DFS
1.全排列问题

/**
     * 全排列问题
     *假设有n个字符要排列，把他们依次放到n个箱子中
     *当前字符有没有访问过（有没有放进之前的箱子里），没有的话，放进当前箱子并标记
     *放另外一个东西时，要把前一个东西释放掉，恢复初始状态，当到n+1个箱子时，一次排列已经结束
     */
    public ArrayList<String> fullPermutation(char[] res){
        ArrayList<String> result =new ArrayList<>();
        if(res.length == 0){
            return  result;
        }
        int[] flag = new int[res.length];
        char[] temp = new char[res.length];
        fullPermutationHelper( res,flag,temp,0, result);
        return result;
    }
public ArrayList<String> fullPermutationHelper(char[] res,int[] flag,char[] temp,int step,ArrayList<String> result){
    //判断边界
    if(step == temp.length){
        result.add(String.valueOf(temp));
        return result;
    }
    //便历每一种可能的情况
    for(int i = 0;i < res.length;i++){
        //第i个字符未被访问过的话，就将其装入当前空箱子
        if(flag[i] == 0){//满足check条件
            temp[step] = res[i];
            //标记为已访问
            flag[i] = 1;
            //递归的把下一个空箱子放好，那么其实下一个空箱子能放的字符其实是从除了temp中前一段已有的
            // 字符外（标记为已被访问），剩下的里面选一个，所以只和前面有关
            fullPermutationHelper( res,flag,temp,step+1, result);
            //回溯，还原，既然当前箱子里接下来要放别的字符了，那么就需要把当前字符释放掉，让后面的箱子使用
            flag[i] = 0;
        }
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2.素数环问题：
如图所示，环由n个圆组成。将自然数1,2，…，n分别放入每个圆中，并且两个相邻圆中的数字总和应为素数。
注意：第一个圆圈的数应该始终为1。

输入格式
输入包含多组测试数据。每组输入占一行，为整数n（0<n<20），表示圆圈数。
输出格式
对于每组输入，输出所有正确的方案，按字典序从小到大排序。每组输出后输出一个空行。具体输出格式见输出样例。
注意：只能按照顺时针方向放置数字。
样例输入

6
8
1
2

样例输出

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
1
2
3
4
5
6
7
8

素数的判断： 我们知道，一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到因数，那么右侧也一定找不到因数
改进1： 不判断偶数因子
改进2： 素数一定在6的倍数的两侧（反过来不成立）

那么只需要判断6的倍数的两侧的数是不是素数，并且只要判断该数能不能被从从5~sqrt(n)的6i-1和6i+1整除就好了，因为该数肯定不能被2或者3整除，也就不可能被6i+2，6i+3，6i+4整除
注意： 用数组存储每一组数据然后直接打印比较好操作，但是把每一次的结果都保存下来的话，用ArrayList的时候要注意，在恢复初始状态时，要把当前值remove掉

/**
 * 判断是否是素数
 */
public boolean isPrimer(int n){
    if(n == 2 || n == 3){
        return true;
    }
    else if(n % 2 == 0 || n <= 1){
        return false;
    }
    //不在6的倍数的两侧
    else if(n % 6 != 1 && n % 6 != 5 ){
        return false;
    }
    //在6的倍数的两侧
    else{
        for(int i = 5;i <= Math.floor(Math.sqrt(n));i+=6){
            if(n % i == 0 || n % (i + 2) == 0){
                return false;
            }
        }
        return true;
    }
}

/**
 *素数环问题
 */
public ArrayList<ArrayList<Integer>> primeRing(int n){
    if(n == 0){
        return null;
    }
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    int[] flag = new int[n+1];
    ArrayList<Integer> temp = new ArrayList<>(n);
    //素数环的第一个圆圈里面的数字始终为1
    temp.add(1);
    flag[0] = 1;
    flag[1] = 1;
    primeRingHelper(1,n,flag,temp,result);
    return result;
 }
 public void primeRingHelper(int step,int n,int[] flag,ArrayList<Integer> temp,ArrayList<ArrayList<Integer>> result){
    //判断边界
     if(step == n){
         result.add(new ArrayList<Integer>(temp));
         return;
     }
     for(int i = 2;i <= n;i++){
         //满足check条件
         if(checkPrimeRing(i,step,n,temp,flag)){
             //标记为已用
             flag[i] = 1;
             //当前数字放进当前圆
             temp.add(i);
             //递归下一个圆
             primeRingHelper(step+1,n,flag,temp,result);
             //回溯，恢复初始状态（换用其他数字了，就要把当前数字释放掉）
             flag[i] = 0;
             temp.remove(step);
         }
     }
     return;
 }

/**
 *判断是否能将当前数字放进当前的圆圈
 */
public boolean checkPrimeRing(int num,int step,int n,ArrayList<Integer> temp,int[] flag){
    //该数字在之前的圆圈中没出现过，并且使得当前圆圈和之前的圆圈里面的数字的和是素数
    if(flag[num] == 0 && isPrimer(num+ temp.get(step - 1))){
        //最后一个圆圈，需要判断和第一个的和
        if(step == n - 1){
            if(!isPrimer(num+ temp.get(0))){
                return false;
            }
        }
        return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

3.油田问题
这就是一个非连通图中数连通分量的问题
题目描述
输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横、竖或者对角线方向），即属于同一个八连块。
输入
输入行数m，列数n。
然后输入*和@
输出
联通块个数
样例输入

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5 
****@
*@@*@
*@**@
@@@*@
@@**@
1
2
3
4
5
6
7
8
9
10
11
12
13
14

样例输出

0
1
2
2
1
2
3
4

知识点： Scanner的next()和nextLine():都返回字符串

• next()不会吸取字符前/后的空格/Tab键，只吸取字符，开始吸取字符（字符前后不算）直到遇到空格/Tab键/回车截止吸取；
• nextLine()吸取字符前后的空格/Tab键，回车键截止。

/**
 * 数连通的油田个数
 */
public int oilDeposits() {
    //键盘输入
    Scanner cin = new Scanner(System.in);
    int m = cin.nextInt();
    int n = cin.nextInt();
    String[] map = new String[m];
    int[][] vis = new int[m][n];
    int count = 0;
    //键盘读入
    for (int i = 0; i < m; i++) {
       map[i] = cin.next();
    }

    //8个方向
    int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            //对每一块油田进行dfs寻找连通分量，找过的油田会被标记，防止重复
            if (vis[i][j] == 0 && map[i].charAt(j) == '@') {
                oilDepositsHelper(map, move,vis,i,j);
                count++;
            }
        }
    }
    return count;
}

/**
 * 对某个坐标进行dfs，查找该处是否有油田的连通分量
 */
public void oilDepositsHelper(String[] map, int[][] move, int[][] vis, int x, int y) {
    int newx = 0;
    int newy = 0;
    //边界条件其实包含在check里了,访问八个方向直到某个非油田的坐标就代表该连通分量访问结束
    if (checkOilDeposits(x, y, map,vis)) {
        //将该油田标记为已访问（算进某个连通分量以后就不会再次访问它了），否则会重复
        vis[x][y] = 1;
        for(int i = 0;i < 8;i++){
            //访问八个方向的坐标
            newx = x + move[i][0];
            newy = y + move[i][1];
            oilDepositsHelper(map,move,vis,newx,newy);
        }
        return;
    }
    return;
}

/**
 * 检查是否该坐标有油田
 */
public boolean checkOilDeposits(int x, int y, String[] map,int[][] vis) {
    //必须判断x和y的范围是否合法，因为8个方向都要检查，所以边界点可能会越界
    if (x >= 0 && x < vis.length && y >= 0 && y < vis[0].length && vis[x][y] == 0 && map[x].charAt(y) == '@') {
        return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

4.棋盘问题
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
输入含有多组测试数据。
每组数据的第一行是两个正整数，n，k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
1
2
3
4
5
6
7
8
9

样例输出

2
1
1
2

/**
 * 棋盘问题
 * @return 所有可能的放置情况
 */
public void checkerBoard(){
    //键盘输入
    Scanner cin = new Scanner(System.in);
    while(cin.hasNext()) {
        int n = cin.nextInt();
        int k = cin.nextInt();
        //截止符号
        if(n == -1 && k == -1){
            break;
        }
        int[] vis = new int[n];
        String[] map = new String[n];
        //键盘读入
        for (int i = 0; i < n; i++) {
            map[i] = cin.next();
        }
        System.out.println(checkerBoardHelper(map,vis,0,k,0));
    }

}
public int checkerBoardHelper(String[] map,int[] vis,int row,int k,int count){
    //边界条件:剩下的需要摆放的棋子数为0
    if(k == 0){
        count++;
        return count;
    }
    //每次都从已经摆放好棋子的下一行开始遍历
    for(int i = row;i < map.length;i++){
        for(int j = 0;j < map[0].length();j++){
            //for循环保证行不重复，check保证列不重复
            if(map[i].charAt(j) == '.' || vis[j] == 1){
                //不满足check直接跳过
                continue;
            }
            //该列标记为已占用
            vis[j] = 1;
            //递归放好剩下的棋子
            count = checkerBoardHelper(map,vis,row+1,k-1,count);
            //恢复状态，回溯（要占用其他列了，把当前列释放掉）
            vis[j] = 0;
        }
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

二、BFS
太累了，先写一个例子吧emmm
典型例子：骑士游历 Knight Moves HDOJ - 1372
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the “difficult” part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

InputThe input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
OutputFor each test case, print one line saying “To get from xx to yy takes n knight moves.”.
**题目大意：**给出一个棋盘，横坐标a_h,纵坐标18，给出两对坐标，问从起点到终点的最少步数，8个方向类似于马走日。
样例输入

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
1
2
3
4
5
6
7
8

样例输出

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
1
2
3
4
5
6
7
8

注意: 因为是连续输入连续输出的处理，vis数组和队列需要放在 while(cin.hasNext())里，每组数据都要刷新才行；感觉这个题要是给出结束符就好了

/**
 * 骑士周游棋盘节点类
 */
class CheckerNode{
    int x;
    int y;
    int step;
    CheckerNode(int x,int y,int step){
        this.x = x;
        this.y = y;
        this.step = step;
    }
}
public class BFSExamples {
    public void knightMoves(){
        //走日八个方向
        int[][] move = {{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2}};
        Scanner cin = new Scanner(System.in);
        while(cin.hasNextLine()){
            String[] res = new String[2];
            //将坐标都转化成整数
            int startX,startY,endX,endY;
            res[0] = cin.next();
            res[1] = cin.next();
            int[][] vis = new int[8][8];
            Queue<CheckerNode> queue = new LinkedList<>();
            //将坐标都转化成整数,横坐标为x
            startX = res[0].charAt(0) - 97;
            startY = res[0].charAt(1) - 49;
            endX = res[1].charAt(0) - 97;
            endY = res[1].charAt(1) - 49;
            queue.offer(new CheckerNode(startX,startY,0));
            //标记为已访问，走过的地方就不要再回头了
            vis[startX][startY] = 1;
            //记录路径
            StringBuffer route = new StringBuffer();
            while (!queue.isEmpty()){
                CheckerNode temp = queue.poll();
                if(temp.x == endX && temp.y == endY){
                    if(route.lastIndexOf("-") >= 0) {
                        route.deleteCharAt(route.lastIndexOf("-"));
                        route.deleteCharAt(route.lastIndexOf(">"));
                    }
                    System.out.println("从" + res[0] + "到" + res[1] + "最短的步数为" + temp.step);
                    System.out.println("路径：" + route);
                    break;
                }
                for(int i = 0;i < 8;i++){
                    int newX = temp.x + move[i][0];
                    int newY = temp.y + move[i][1];
                    if(!checkknightMoves(vis,newX,newY)){
                        //不满足条件的直接跳过
                        continue;
                    }
                    queue.offer(new CheckerNode(newX,newY,temp.step + 1));
                    //System.out.println("push");
                    vis[newX][newY] = 1;
                    route.append('[');
                    route.append((char)(newX + 97));
                    route.append((char)(newY + '0' + 1));
                    route.append(']');
                    route.append("->");
                }
            }
        }
        return;
    }

    /**
     *该座标是否可以走
     */
   public boolean checkknightMoves(int[][] vis,int x,int y){
        if(x >= 0 && x < 8 && y >= 0 && y < 8 && vis[x][y] == 0){
            return true;
        }
        return false;
   }
     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78