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。
        }
    }
}

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

---