DFS

以 N 皇后 问题为例

class DFS {
  final static int N = 10010l;
  final static char[][] p = new char[N][N];
  final static boolean[] row = new boolean[N], col = new boolean[N], dg = new boolean[N], udg = new boolean[N];
  
  private static void dfs(int u, int n) {
    if (u == n) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          System.out.print(p[i][j] + " ");
        }
        System.out.println();
      }
      System.out.println();
      return ;
    }
    
    for (int i = 0; i < n; i++) {
      if (!(col[i] || dg[i + u] || udg[n - u + i])) {
        q[u][i] = 'Q';
        col[i] = dg[i + u] = udg[n - u + i] = true;
        dfs(u + 1, n);
        col[i] = dg[i + u] = udg[n - u + i] = false;
        q[u][i] = '.';
      }
    }
  }
  
  private static void dfs(int x, int y, int s, int n) {
    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(p[i][j] + " ");
          }
          System.out.println();
        }
        System.out.println();
      } 
      return;
    }
    
    dfs(x, y + 1, s, n);
    
    if (!(row[x] || col[y] || dg[x + y] || udg[x - y + n])) {
      q[x][y] = 'Q';
      row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
      dfs(x, y + 1, s + 1, n);
      col[i] = dg[i + u] = udg[n - u + i] = false;
      q[u][i] = '.';
    }
  }
  
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt();
    
    for (var i : p) Arrays.fill(i, '.');
    
    dfs(0, n);
    // dfs(0, 0, 0, n);
  }
}

BFS

以 图的最短路径 为例

class BFS {
  final static int N = 10010;
  final static int[][] g = new int[N][N], d = new int[N][N];
  final static PII[] q = new PII[];
  final static PII[][] prev = new PII[N][N];
  
  private static int bfs(int n) {
    int hh = 0, tt = 0;
    for (int i = 0; i< n; i++) Arrays.fill(d[i], -1);
    q[0] = new PII(0, 0);
    int[] dx = {0, 0, -1, 1}, dy = {1, -1, 0, 0};
    d[0][0] = 0;
    
    while (hh <= tt) {
      var t = q[hh++];
      for (int i = 0; i < 4; i++) {
        int x = t.first + dx[i], y = t.second + dy[i];
        // 确保 x, y 坐标合法                     [x, y]位置上可以前进 [x, y]未被访问过
        if (x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0 && d[x][y] == -1) {
          d[x][y] = d[t.first][t.second];
          // 记录前驱节点
          prev[x][y] = t;
          q[++tt] = new PII(x, y);
        }
      }
    }
    
    // 遍历路径
    int x = y = n - 1;
    while (x != 0 || y != 0) {
      System.out.println("[" + x + "," + y + "] <- ");
      var t = prev[x][y];
      x = t.first; y = t.second;
    }
    
    return d[n - 1][n - 1];
  }
  
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt();
    
    for (int i = 0; i < n; i++) 
      for (int j = 0; j < n; j++) 
        g[i][j] = cin.nextInt();
    
    System.out.println(bfs(n));
  }
}

图的存储

class SaveGraph {
  final static int N = 10010;
  static int idx = 0;
  final static int[] h = new int[N], e = new int[N], ne = new int[N];
  
  private static int insert(int a, int b) {
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
  }
  
  private static void traverse(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) 
      System.out.print(i + " -> ");
  }
}

• 参考来源
  • ACWing - 算法基础课