DFS

stack【递归也是栈】 o(h) h = 深度，空间稍微少一点，不具有最短性。
回溯、剪枝
对空间要求比较高。
考虑顺序！ 俗称暴搜

全排列

回溯的时候要恢复现场

剑指offer 38. 字符串的排列
class Solution {
    private  Set<String> res;
    private  boolean[] visited;
    private  char[] temp;
    public  String[] permutation(String s) {
        res = new HashSet<>();
        visited = new boolean[s.length()];
        temp = new char[s.length()];
        dfs(s,0);
        return res.toArray(new String[res.size()]);
    }
    private  void dfs(String s,int index) {
        if (index >= s.length()) {
            res.add(new String(temp));
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if (!visited[i]) { 
                visited[i] = true;
                temp[index] = s.charAt(i);
                dfs(s, index + 1);
                visited[i] = false;
            }
        }
    }

}

leetcode 46
class Solution {
    private List<List<Integer>> res;
    private boolean[] visited;
    private int[] temp;
    private int[] nums;
    public List<List<Integer>> permute(int[] nums) {
        res = new LinkedList();
        temp  = new int[nums.length];
        visited = new boolean[nums.length];
        this.nums = nums;
        dfs(0);
        return res;
    }
    private void dfs(int index) {

        if(index >= nums.length) {
            List<Integer> list = new LinkedList();
            for (int i : temp) {  
                list.add(i);
            }
            res.add(list);
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                temp[index] = nums[i];
                dfs(index + 1);
                visited[i] = false;
            }
        }

    }

}

BFS

queue o(2^h) 存放的是每一层的节点 空间相对于多一点， 第一次扩展到的点-最短路。
宽搜伪代码： 初始状态放入queue，
while queue不空
拿出队头
扩展队头
从距离数组直接拿到数据

走迷宫

//很多时候我们都要去定义一个pair来保存一个节点的key value 
class Pair{
    int key;
    int value;
    Pair(int k,int v){key=k;value=v;}
    public int getKey(){return key;}
    public int getValue(){return value;}
}
class Main{
    private static int n,m;
    private static int[][] p,d;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();m=sc.nextInt();
        p=new int[n][m];
        d=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                p[i][j]=sc.nextInt();
                //距离值的初始值设为-1用于判断是否遍历过
                d[i][j]=-1;
            }
        }
        System.out.println(bfs());
    }
    //
    public static int bfs(){
        //队列初始化
        Queue<Pair> q=new LinkedList<>();
        //把（0，0）插入队头
        q.add(new Pair(0,0));
        int[] dx={-1,0,1,0},dy={0,1,0,-1};
        while(!q.isEmpty()){
            //取并弹出队头元素
            Pair t=q.poll();
            for(int i=0;i<4;i++){
                int x=t.getKey()+dx[i],y=t.getValue()+dy[i];
                //坐标不越界 && 没被遍历过 && 值为0
                if(x>=0 && x<n && y>=0 && y<m && p[x][y]==0 && d[x][y]==-1){
                    //赋为前一个点的值+1
                    d[x][y]=d[t.getKey()][t.getValue()]+1;
                    q.add(new Pair(x,y));
                }
            }
        }
        //距离起始为-1，最终要+1
        return d[n-1][m-1]+1;
    } 
}

拓扑序列

本身是有向无环图的宽度优先遍历的应用

存在环的话，一定有点的入度不为0
一个有向无环图，一定至少存在一个入度为0的点。