1、深度优先搜索（DFS）

顺序

剪枝

题目一

求n个数的所有排序
输入
3
输出
123
132
213
231
321
312

代码

public class DFS {
    final static int N =100010;
    static int[] path = new int[N];
    static boolean[] st = new boolean[N];
    static int n;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dfs(0);
    }
    private static void dfs(int u) {
        if (u == n) {
            for (int i = 0; i < n; i++) System.out.print(path[i] + " ");
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) { //递归
            if (!st[i]) {
                path[u] = i;
                st[i] = true;
                dfs(u+1);
                st[i] = false;
            }
        }
    }
}

题目二

N-皇后问题

2、宽度优先搜索(BFS)

题目

给定一个nm的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。
最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。
数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。
输入格式
第一行包含两个整数n和m。
接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8
*代码展示

public class Main {
    static int n,m;//记录地图大小
    static int[][] map = null;//记录地图
    static int[][] d = null;//记录走的距离
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        n = Integer.parseInt(strs[0]);
        m = Integer.parseInt(strs[1]);
        map = new int[n][m];
        d = new int[n][m];
        for (int i = 0; i < n; i++) {
            strs = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(strs[j]);
            }
        }
        System.out.println(dfs());
    }
    private static int dfs() {
        Queue<Pair> q = new LinkedList<Pair>();
        /**
           *    判断上下左右是否符合规范
        */
        int[] dx = {1,0,-1,0},dy = {0,-1,0,1};
        q.offer(new Pair(0,0));
        while (!q.isEmpty()) {
            Pair p = q.poll();
            if (p.x == n-1 && p.y == m -1) break;
            for (int i = 0; i < 4; i++) {
                int x = p.x + dx[i];
                int y = p.y + dy[i];
                if (x >= 0 && x < n && y >=0 && y < m && d[x][y] == 0 && map[x][y] == 0) {
                    q.offer(new Pair(x,y));
                    d[x][y] = d[p.x][p.y] + 1;
                }
            }
        }
        return d[n-1][m-1];
    }
}
class Pair{
    public int x;
    public int y;
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

3、树与图的存储

4、树与图的深度优先遍历

题目

重心树

5、树与图的宽度优先遍历

题目

6、拓扑排序

题目