算法模板（Java版）_DFS与BFS-EW帮帮网

@ZZHow(ZZHow1024)

搜索方式	数据结构	空间	特点
DFS	Steak	$O (h)$	不具有最短路
BFS	Queue	$O(2 ^ h)$	最短路

DFS

DFS（深度优先搜索），回溯时记得回复现场。

必要时进行剪枝操作。

例题：AcWing 842. 排列数字

import java.util.Scanner;

public class Main {
    static int n;
    static int[] path;
    static boolean[] st;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        path = new int[n + 1];
        st = new boolean[n + 1];
        
        dfs(0);
    }
    
    public 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 = 1; i <= n; i++) {
            if (!st[i]) {
                st[i] = true;
                path[u] = i;
                dfs(u + 1);
                st[i] = false;
            }
        }
    }
}

例题：AcWing 843. n-皇后问题

按行搜索

import java.util.Scanner;

public class Main {
    static final int N = 20;
    static int n;
    static char[][] g = new char[N][N];
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[N];
    static boolean[] udg = new boolean[N];
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = '.';
        
        dfs(0);
    }
    
    public static void dfs(int u) {
		    // 搜索出一组答案
        if (u == n) {
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++)
                    System.out.print(g[i][j]);
                System.out.println();
            }
            System.out.println();
        }
        
        // 枚举一行可以放棋子的位置
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
                g[u][i] = 'Q';
                col[i] = dg[u + i] = udg[n - u + i] = true;
                dfs(u + 1);
                col[i] = dg[u + i] = udg[n - u + i] = false;
                g[u][i] = '.';
            }
        }
    }
}

按格子依次搜索

import java.util.Scanner;

public class Main {
    static final int N = 20;
    static int n;
    static char[][] g = new char[N][N];
    static boolean[] row = new boolean[N];
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[N];
    static boolean[] udg = new boolean[N];
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = '.';
        
        dfs(0, 0, 0);
    }
    
    public static void dfs(int x, int y, int s) {
        // 行出界
        if (y == n) {
            y = 0;
            x++;
        }
        
        // 搜索出一组答案
        if (x == n) {
            if (s == n) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++)
                        System.out.print(g[i][j]);
                    System.out.println();
                }
                System.out.println();
            }
            
            return;
        }
        
        // 不放皇后
        dfs(x, y + 1, s);
        
        // 放皇后
        if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
            g[x][y] = 'Q';
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
            dfs(x, y + 1, s + 1);
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
            g[x][y] = '.';
        }
    }
}

BFS

BFS（宽度优先搜索），使用队列。

例题：AcWing 844. 走迷宫

import java.util.Scanner;

public class Main {
    static final int N = 110;
    static int n;
    static int m;
    static int[][] g = new int[N][N];
    static int[][] d = new int[N][N];
    static Pair[] q = new Pair[N * N];
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        m = scanner.nextInt();
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                g[i][j] = scanner.nextInt();
                
        System.out.println(bfs());
    }
    
    public static int bfs() {
        // 队头
        int hh = 0;
        // 队尾
        int tt = 0;
        
        q[0] = new Pair(0, 0);
        
        for (int i = 0; i < d.length; i++)
            for (int j = 0; j < d[i].length; j++)
                d[i][j] = -1;
        
        d[0][0] = 0;
        
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        
        while (hh <= tt) {
            Pair t = q[hh++]; // 取出队头
            
            for (int i = 0; i < 4; i++) {
                int x = t.first + dx[i];
                int y = t.second + dy[i];
                
                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
                    d[x][y] = d[t.first][t.second] + 1;
                    q[++tt] = new Pair(x, y);
                }
            }
        }
        
        return d[n - 1][m - 1];
    }
}

class Pair {
    public int first;
    public int second;
    
    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

树与图的深度优先遍历

树是一种特殊的图（无环连通图）

有向图的存储方法

邻接矩阵
邻接表

例题：AcWing 846. 树的重心

import java.util.Scanner;

public class Main {
    static final int N = 100010;
    static final int M = N * 2;
    static int n;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static boolean[] st = new boolean[N];
    static int idx = 0;
    static int ans = N;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        
        for (int i = 0; i < h.length; i++)
            h[i] = -1;
        
        for (int i = 0; i < n - 1; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            
            add(a, b);
            add(b, a);
        }
        
        bfs(1);
        
        System.out.println(ans);
    }
    
    public static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    public static int bfs(int u) {
        st[u] = true;
        
        int sum = 1; // 当前子树的大小
        int res = 0; // 删除当前点后连通块的最大值
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            
            if (!st[j]) {
                int s = bfs(j);
                res = Math.max(res, s);
                sum += s;
            }
        }
        
        res = Math.max(res, n - sum);
        ans = Math.min(ans, res);
        
        // 返回当前子树的大小
        return sum;
    }
}

树与图的广度优先遍历

重边：两个点之间有两条边

自环：一条边指向自己

例题：AcWing 847. 图中点的层次

import java.util.Scanner;

public class Main {
    static final int N = 100010;
    static int n;
    static int m;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int idx = 0;
    static int[] q = new int[N];
    static int[] d = new int[N];
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        m = scanner.nextInt();
        
        for (int i = 0; i <= n; i++)
            h[i] = -1;
        
        while (m-- != 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            
            add(a, b);
        }
        
        System.out.println(bfs());
    }
    
    public static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    public static int bfs() {
        int hh = 0;
        int tt = 0;
        
        for (int i = 0; i <= n; i++)
            d[i] = -1;
        
        q[0] = 1;
        d[1] = 0;
        
        while (hh <= tt) {
            int t = q[hh++];
            
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                
                if (d[j] == -1) {
                    d[j] = d[t] + 1;
                    q[++tt] = j;
                }
            }
        }
        
        return d[n];
    }
}

有向图的拓扑序列

例题：AcWing 848. 有向图的拓扑序列

import java.util.Scanner;

public class Main {
    static final int N = 100010;
    
    static int n;
    static int m;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int idx = 0;
    static int[] q = new int[N];
    static int[] d = new int [N];
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        m = scanner.nextInt();
        
        for (int i = 0; i <= n; i++)
            h[i] = -1;
        
        while (m-- != 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            
            add(a, b);
            d[b]++;
        }
        
        if (topSort()) {
            for (int i = 0; i < n; i++)
                System.out.print(q[i] + " ");
        } else {
            System.out.println("-1");
        }
    }
    
    public static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    public static boolean topSort() {
        int hh = 0;
        int tt = -1;
        
        for (int i = 1; i <= n; i++)
            if (d[i] == 0)
                q[++tt] = i;
        
        while (hh <= tt) {
            int t = q[hh++];
            
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                
                d[j]--;
                if (d[j] == 0)
                    q[++tt] = j;
            }
        }
        
        return tt == n - 1;
    }
}

算法模板（Java版）_DFS与BFS

DFS

BFS

树与图的深度优先遍历

树与图的广度优先遍历

有向图的拓扑序列

网站公告

今日签到

热门文章

最新发布