前言

对于二叉树和图的遍历而言，我们很难避开两种算法DFS(深度优先搜索)和BFS(广度优先搜索)。网盘搜索

DFS

全称Depth First Search，从根节点开始一直沿着一个路径(左子树或右子树)走到底，直到走不通了(叶子节点)，返回上一个父节点，接着继续相同路径(左子树、右子树)走，直到最终退回到根节点，搜索结束。这种尽量往深处搜索的方式就叫深度优先DFS。很像栈的后进先出，所以深度优先搜索一般都是用栈来实现。方法栈“天然”的栈，递归就是利用方法栈。二叉树的先、中、后序遍历，因为恰好需要栈来实现。

运用

全排列

	/**
     * 排列公式的推出，穷举法：
     * 1.先从所有n个待排元素中选取一个放在第一位index=0，有n种可能
     * 2.从剩余的n-1种选一个放在index=1的位置，有n-1种可能
     * 3.依次下去n(n-1)(n-2)...2*1
     * 那么我们穷举出所有排列
     * 遍历序列nums让nums[0]放在fixing=0的位置固定，nums[1~n]递归调用nums[1]放在fixing=1的位置
     * 当fixed等于数组长度-1时，意味着本轮穷举结束，出栈对上一个栈fied=nums.length-2进行固定。依次类
     * 推，直到所有的栈都退出，就拿出所有可能排列。
     * @param nums 待排列序列
     * @param fixed fixed指针及左侧都是排好顺序的不能动。fixed=-1意味着还没有开始占位。
     * @param result 排序后的序列集合
     * @return
     */
    public static List<List<Integer>> permuteHelper(int[] nums,int fixed,List<List<Integer>> result) {
        //fixed指向的是已固定位置下标，当固定位置指向nums.length-1位置时，本轮排序结束
        if(fixed == nums.length-1){
            result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
            return result;
        }
        /**
         * 针对nums横向遍历【5,4,6,2】
         * fixed，它以及之前的位置已经固定了
         * fixing本轮循环将要固定的位置,只能用fiexd之后的元素来填充。
         */
        for (int i = fixed+1,fixing = i; i < nums.length; i++) {
            //固定位置本身元素可以填充该位置，不需要交换。它之后位置上的来填充需要和该位置交换
            if(i != fixing) {//@*
                swap(nums, fixing, i);
            }
            //固定位后移一位，递归固定后的数组
            permuteHelper(nums,fixing,result);
            /**恢复nums数组,防止横向遍历时取出重复数字来固定。能到这里表明
             * 上一栈退出了，回到当前栈，就要恢复nums数据，因为进入上一个栈之前我
             * 们(在@*)有可能swap了数据，所以要恢复后才能横向继续找可以填充固定
             * 位的数值。
             */
            if(i != fixing) {
                swap(nums, fixing, i);
            }
        }
        return result;
    }
    public static  List<List<Integer>> permute(int [] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        permuteHelper(nums,-1,result);
        return result;
    }
    public static  void swap(int []x,int a,int b){
        int temp = x[a];
        x[a] = x[b];
        x[b] = temp;
    }
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

BFS

全称Breadth-First-Search，从根节点开始依次(左->右或右->左)访问它的相邻节点(深度差为1)，同一深度节点访问完。继续依次访问相邻节点的相邻节点。直到访问到最后一个叶子节点结束。那么我们就需要一个容器来存储每一层遍历过的节点，以便遍历他们的下一层；我们还需要记住对应层级，这样才能依照层级从小到到大依次取出遍历的元素。map(level,List)貌似可以，如果是挑选层级(3,4,2,1)来使用，是一个不错选择。但是一般都是按层级大小依次取出元素，所以相当于遍历map，它的效率低于list遍历。那么最原始的就是二元组。List>这里刚好用外层数组index+1来代表层级。最常见的应用二叉树的层序遍历。

比较

1. 简单理解DFS纵向深度搜索,BFS广度优先横向宽度搜索。
2. DFS运用栈的后进先出特性，BFS运用队列先进先出。
3. DFS运用栈特性，“一条道走到黑”，那么深度越深，时间复杂度越高。
   BFS需要额外空间存储查询出来的相邻节点，假设每个节点衍生子节点为N个，总节点个数$\frac{(1-N{)}^{leve-1}}{1-N}$,当深度和衍生个数相当大时，需要很大的内存空间。

应用

DFS 一般是解决连通性问题。 BFS 一般是解决最短路径问题。