DFS(深度优先搜索)和BFS(宽度优先搜索)

目录

DFS（深度优先搜索）

全排列的DFS解法

 利用DFS递归构建二进制串和递归树的结构剖析

DFS--剪枝

DFS例题--整数划分

 BFS(宽度优先搜索)

 全排列的BFS解法

---

DFS（深度优先搜索）

        深度优先搜索（Depth First Search，DFS）是十分常见的图搜索方法之一。深度优先搜索会沿着一条路径一直搜索下去，在无法搜索时，回退到刚刚访问过的节点。深搜优先搜索的本质上就是持续搜索，遍历了所有可能的情况。DFS搜索的流程是一个树的形式，每次一条路走到低。

全排列的DFS解法

public class DFS {public static void main(String[] args) {DFS(0, "", 3);}public static void DFS(int depth, String ans, int n) {if (depth == n) {//深度等于n时就输出System.out.print(ans + " ");return;}for (int i = 1; i <= n; i++) {DFS(depth + 1, ans + i, n);           }}
}

如果不对其进行剪枝操作，就会将所有的子叶全部输出

 所以在需要要求全排列的情况下我们就需要进行剪枝，也就是对递归循环进行判断

public class DFS {public static void main(String[] args) {DFS(0, "", 3);}public static void DFS(int depth, String ans, int n) {if (depth == n) {//深度等于n时就输出System.out.print(ans + " ");return;}for (int i = 1; i <= n; i++) {if (! ans.contains("" + i)) {//目前已经生成的ans串用过的不能再用(剪枝)DFS(depth + 1, ans + i, n);}//public boolean contains(CharSequence s)// 当且仅当此字符串包含指定的 char 值序列时，返回 true。}}
}

这样得到的结果就是全排列后的结果了

---

 

 

 利用DFS递归构建二进制串和递归树的结构剖析

二进制串0000 -> 1111的所有可能

public class binaryStringRecurrence {public static void main(String[] args) {DFS(0, "");//从0层开始}public static void DFS(int depth, String binary) {//depth为深度，binary为求出的二进制串System.out.printf("%sdg(%d, %s)\n", Lpad(depth), depth, binary);//用来查看各个节点if (depth == 4) {//深度为4的时候输出字符串System.out.println(binary);return;}//每次开枝散叶都需要开2支，左边补0，右边补1DFS(depth + 1, binary + "0");DFS(depth + 1, binary + "1");}public static String Lpad(int n) {//用来打印空格String ans = "";for (int i = 1; i <= n; i++) {ans += "        ";}return ans;}
}

代码执行流程，可以看出DFS递归的流程以及开枝散叶的方式

dg(0, )
        dg(1, 0)
                dg(2, 00)
                        dg(3, 000)
                                dg(4, 0000)
0000
                                dg(4, 0001)
0001
                        dg(3, 001)
                                dg(4, 0010)
0010
                                dg(4, 0011)
0011
                dg(2, 01)
                        dg(3, 010)
                                dg(4, 0100)
0100
                                dg(4, 0101)
0101
                        dg(3, 011)
                                dg(4, 0110)
0110
                                dg(4, 0111)
0111
        dg(1, 1)
                dg(2, 10)
                        dg(3, 100)
                                dg(4, 1000)
1000
                                dg(4, 1001)
1001
                        dg(3, 101)
                                dg(4, 1010)
1010
                                dg(4, 1011)
1011
                dg(2, 11)
                        dg(3, 110)
                                dg(4, 1100)
1100
                                dg(4, 1101)
1101
                        dg(3, 111)
                                dg(4, 1110)
1110
                                dg(4, 1111)
1111

进程已结束,退出代码0

---

DFS--剪枝

剪枝是DFS中的一个判断技巧，就是把不会产生答案的或者不必要的的枝条剪掉。剪枝的关键是剪哪一条枝，在哪个地方减。

将整数n分成k份，每份不能为空，任意两种划分方案不能相同(不考虑顺序)

例如：n = 7，k = 3，下面三种划分方案被认为是相同的

115    151    511

import java.util.Scanner;public class nDivideK {public static int ans;//记录成功方案的次数public static int cnt;//记录DFS调用的次数public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {int n = scanner.nextInt();//被划分数int k = scanner.nextInt();//规定划分份数DFS(n, k, 1, "");//i初始为1，因为第一次最小可用值就是1System.out.println("方案数为：" + ans);System.out.println("DFS调用的次数为：" + cnt);}}/*** 整数n划分k份的方案* @param n 被划分数* @param k 规定划分份数* @param min 保证构造非降序，如 1 1 5和 5 1 1是 等价的。表示目前被拆分使用的最大数,下次拆分可用的最小值* @param fangan 记录划分方案次数*/public static void DFS(int n, int k, int min, String fangan) {cnt++;//只要DFS被调用cnt就自增if (k == 1 && min <= n) {//这里min需要小于等于n，要不无法继续拆解ans++;//找到正确的方案，ans就自增System.out.println(fangan + n);return;}if (min * k > n) return;//剪枝//开枝散叶for (int i = min; i <= n ; i++) {DFS(n - i, k - 1, i, fangan + i +"+");//n-i为拆分后的数，k-1为剩余的拆分次数，i为下次可用的最小值}}
}

 运行结果：

---

DFS例题--整数划分

一个整数可以划分成若干个不超过自己的整数之和的形式，例如：

4

4=1+1+1+1

4=1+1+2

4=1+3

4=2+2

4=4

总共有5种划分形式，约定

1）这些加数必须遵循从小到大原则

2）4=1+3和4=3+1当做一种划分

public class DFSIntSplit {public static void main(String[] args) {int n = 4;DFS(n, 0, 0, "");}/**** @param n 被拆分的数* @param nowget 目前已经得到的值* @param maxused 记录目前拆分已经使用的最大值* @param ans 拆分方案*/public static void DFS(int n, int nowget, int maxused, String ans) {if (nowget == n) {//当已经得到的值等于被拆分的数时就结束System.out.println(n + "=" + ans);return;}//开枝散叶for (int i = 1; i <= n - nowget ; i++) {//需要累加到n，已经累加到了nowget，所以要n - nowgetif (i >= maxused && i == n - nowget) {//i必须大于当前拆分的最大值才可以继续递归//如果是最后一次循环(i==n-nowget)，那么ans + i就不需要再加 "+" 了DFS(n, nowget + i, i, ans + i);} else if (i >= maxused) {DFS(n, nowget + i, i, ans + i + "+");}}}
}

得到结果：

 BFS(宽度优先搜索)

        宽度优先搜索（Breadth First Search，BFS）它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则拓展第二层结点。如此依次拓展，检查下去，直至发现目标结点为止。如果拓展完所有结点，都没有发现目标结点，则问题无解。

 全排列的BFS解法

        BFS求全排列需要用到队列，首先将1 2 3三个根节点放入队列，每次弹出一个队列头，同时将此队列头对应的两个子叶入列。

import java.util.LinkedList;
import java.util.Queue;public class BFS {public static void main(String[] args) {int n = 3;Queue<String> queue = new LinkedList<String>();for (int i = 1; i <= n; i++) {//将1 2 3入队列queue.offer("" + i);}while (!queue.isEmpty()) {//如果队列不为空就循环//public boolean isEmpty()// 当且仅当 length() 为 0 时返回 true。//返回：如果 length() 为 0，则返回 true；否则返回 false。String head = queue.poll();//弹出列头for (int i = 1; i <= n; i++) {if (head.contains("" + i)) continue;//如果head包含i，就不扩展了String son = head + i;//子叶等于列头+iif (son.length() == n) System.out.println(son);//长度为n说明就产生了三阶的全排列了，就输出else queue.offer(son);//否则就将son入队列}}}
}