BFS is commonly used to solve shortest path problems. Whenever the problem mentions "shortest", it's worth considering whether BFS can be applied.BFS is suitable for problems where edge weights are either 0 or 1. If all edge weights are 1, BFS can be directly applied. If there are edge weights of 0, then bidirectional BFS is needed, or Dijkstra's algorithm can be used.In BFS, there are two main types: single-source BFS and multiple-source BFS. Single-source BFS starts from one source and expands the search layer by layer. Multiple-source BFS allows expanding the search simultaneously from multiple sources, ensuring the correctness of the algorithm.

class Solution {    public int minDepth(TreeNode root) {        if (root == null) {            return 0;        }        int res = 1;        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        while (!queue.isEmpty()) {            int qSize = queue.size();            for (int i = 0; i < qSize; i++) {                TreeNode node = queue.poll();                if (node.left == null && node.right == null) {                    return res;                }                if (node.left != null) {                    queue.offer(node.left);                }                if (node.right != null) {                    queue.offer(node.right);                }            }            res++;        }        return 0;    }}

5 1005 4 5 2 3

1 2 3 4 5

import java.util.*;public class Main {    static final int N = 100010;    static List<Integer>[] g = new ArrayList[N]; // Adjacency list representation of the graph    static long n, k; // Number of nodes and maximum depth    static long[] w = new long[N]; // Values of nodes    static boolean[] st = new boolean[N]; // Array to mark visited nodes    /**     * Perform breadth-first search (BFS) on the graph.     * Start from node 1 and mark nodes visited within the given depth limit.     */    static void bfs() {        st[1] = true; // Mark node 1 as visited        Queue<Integer> q = new LinkedList<>(); // Queue for BFS        q.add(1); // Add node 1 to the queue        long depth = 0; // Initialize depth        while (!q.isEmpty()) {            int sz = q.size(); // Get the size of the current level            depth++; // Increment depth for the next level            for (int i = 0; i < sz; i++) {                int t = q.poll(); // Dequeue the node                for (int x : g[t]) { // Traverse neighbors of the dequeued node                    if (!st[x] && depth < k) { // If neighbor is not visited and within depth limit                        st[x] = true; // Mark neighbor as visited                        q.add(x); // Add neighbor to the queue                    }                }            }        }    }    private static void dfs(int u) {        if (st[u]) return; // If node is visited, return        st[u] = true; // Mark node as visited        for (Integer x : g[u]) { // Traverse neighbors of the current node            dfs(x); // Recursively visit unvisited neighbors        }    }    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        n = sc.nextLong(); // Read the number of nodes        k = sc.nextLong(); // Read the maximum depth        for (int i = 1; i <= n; i++) {            w[i] = sc.nextLong(); // Read the value of each node        }        for (int i = 1; i <= n; i++) {            g[i] = new ArrayList<>(); // Initialize adjacency list for each node            g[i].add((int) w[i]); // Add the value of the node as a neighbor        }        bfs(); // Perform BFS traversal//     dfs(1);         for (int i = 1; i <= n; i++) {            if (st[i]) { // If node is visited                System.out.print(i + " "); // Print the visited node            }        }    }}

Input430 10 20 3223Output0->1

Input760 10 31 23 41 55 614Output0->1->2

import java.util.*;public class Main {    // Define constants    static final int N = 10010;    static int n, m, q;    // Visited array to mark if a node has been visited    static boolean[] st = new boolean[N];    // Adjacency list representation of the graph    static ArrayList<ArrayList<Integer>> g = new ArrayList<>();    // Distance array to record the shortest distance from each node to the start    static int[] dist = new int[N], father = new int[N];    // BFS traversal    static int bfs() {        Queue<Integer> queue = new LinkedList<>();        queue.offer(0);        if (st[0]) return -1;        st[0] = true;        Arrays.fill(dist, Integer.MAX_VALUE);        dist[0] = 0;        while (!queue.isEmpty()) {            int t = queue.poll();            if (g.get(t).size() == 1 && father[t] == g.get(t).get(0)) return t;            for (int x : g.get(t)) {                if (st[x]) continue;                father[x] = t;                queue.offer(x);                dist[x] = dist[t] + 1;                st[x] = true;            }        }        return -1;    }    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        // Read data        n = sc.nextInt(); // Number of intersections        m = sc.nextInt(); // Number of roads        for (int i = 0; i < n; i++) g.add(new ArrayList<>());        while (m-- > 0) {            int a = sc.nextInt(), b = sc.nextInt();            g.get(a).add(b);            g.get(b).add(a);        }        q = sc.nextInt(); // Number of blocked intersections        while (q-- > 0) {            int a = sc.nextInt(); // Blocked intersection number            st[a] = true; // Mark the intersection as blocked        }        // Sort the graph        for (ArrayList<Integer> t : g) Collections.sort(t);        int t = bfs();        if (t == -1) System.out.println("NULL");        else {            // Output the path            ArrayList<Integer> path = new ArrayList<>();            while (t != 0) {                path.add(t);                t = father[t];            }            path.add(0);            Collections.reverse(path);            for (int i = 0; i < path.size(); i++) {                if (i > 0) System.out.print("->");                System.out.print(path.get(i));            }        }    }}

321 0 1 22 1 2 0100 100 100100 000 100000 000 001

1

import java.util.*;// Node class to represent a position in the maze and its time stateclass Node {    int x, y, time; // x and y are the coordinates, time is the current time    Node(int x, int y, int time) {        this.x = x;        this.y = y;        this.time = time;    }}public class Main {    static final int N = 110; // Maximum maze size    static int[] dx = {-1, 1, 0, 0, 0}, dy = {0, 0, 1, -1, 0}; // Direction array, including up, down, left, right, and staying in place    static int[][][] dist = new int[N][N][3]; // 3D array to store the shortest time to reach each point, third dimension is the state (0, 1, 2)    static boolean[][] g = new boolean[N][N]; // Records the position of traps    static String[][] state = new String[N][N]; // Records the wall state cycle at each position    static int n, k, sx, sy, ex, ey; // Maze size, number of traps, start and end coordinates    // BFS to find the shortest path    static int bfs() {        // Initialize the distance array to infinity        for (int[][] row : dist)             for (int[] col : row)                 Arrays.fill(col, Integer.MAX_VALUE);        // Initial state at the start position        dist[sx][sy][0] = 0;        Queue<Node> queue = new LinkedList<>();        queue.offer(new Node(sx, sy, 0));        while (!queue.isEmpty()) {            Node t = queue.poll();            if (t.x == ex && t.y == ey) return t.time; // If the end is reached, return the time            int x = t.x, y = t.y, time = t.time;            for (int i = 0; i < 5; i++) { // Includes four directions and staying in place                int a = dx[i] + x, b = dy[i] + y, next_time = time + 1;                // Check if the new position is valid and has no trap or obstacle                if (a < 0 || a >= n || b < 0 || b >= n || g[a][b] || state[a][b].charAt(next_time % 3) == '1')                     continue;                // If the new state time is shorter, update the distance and add to the queue                if (dist[a][b][next_time % 3] > dist[x][y][time % 3] + 1) {                    dist[a][b][next_time % 3] = dist[x][y][time % 3] + 1;                    queue.offer(new Node(a, b, next_time));                }            }        }        return -1; // If the end cannot be reached, return -1    }    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        n = sc.nextInt();        k = sc.nextInt();        // Read the trap positions        for (int i = 0; i < k; i++) {            int a = sc.nextInt(), b = sc.nextInt();            g[a][b] = true;        }        // Read the start and end positions        ex = sc.nextInt();        ey = sc.nextInt();        sx = sc.nextInt();        sy = sc.nextInt();        // Read the wall state cycle at each position        for (int i = 0; i < n; i++)             for (int j = 0; j < n; j++)                 state[i][j] = sc.next();        // Output the shortest time        System.out.println(bfs());    }}

2 12 11 2

0 0

3 41 2 31 22 3

2 3

import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Queue;import java.util.Scanner;public class Main {    // Constant for maximum number of squares    static final int N = 500010;        // Global variables    static int n, m, res, minv;    static int[] w = new int[N]; // Number of horses in each square    static boolean[] st = new boolean[N]; // Record visited squares    static ArrayList<ArrayList<Integer>> g = new ArrayList<>(N); // Adjacency list representation        // Breadth-First Search (BFS) function    public static void bfs() {        // Initialize the queue        Queue<int[]> queue = new ArrayDeque<>();        // Add the starting square to the queue, with depth 1 and remaining horse feed m minus the feed needed for square 1        queue.add(new int[] {1, 1, m - w[1]});        st[1] = true; // Mark the starting square as visited                // BFS traversal        while (!queue.isEmpty()) {            int[] curr = queue.poll(); // Take the front element from the queue            int d = curr[0]; // Current depth            int u = curr[1]; // Current square            int val = curr[2]; // Remaining horse feed                        // Traverse all neighboring squares of the current square            for (int x : g.get(u)) {                // If the neighboring square is visited or there is insufficient horse feed, skip it                if (st[x] || val < w[x]) continue;                                // Update the result: if a better path is found, update res and minv                if (res < d + 1) {                    res = d + 1;                    minv = m - (val - w[x]);                } else if (res == d + 1) {                    minv = Math.min(minv, m - (val - w[x]));                }                                // Add the neighboring square to the queue, update the remaining horse feed, and mark it as visited                queue.add(new int[] {d + 1, x, val - w[x]});                st[x] = true;            }        }    }    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        n = scanner.nextInt(); // Read the number of squares        m = scanner.nextInt(); // Read the number of portions of horse feed                // Initialize the adjacency list        for (int i = 0; i < N; i++) {            g.add(new ArrayList<>());        }                // Read the number of horses in each square        for (int i = 1; i <= n; i++) {            w[i] = scanner.nextInt();        }                // Read the road information between squares and construct the adjacency list        for (int i = 0; i < n - 1; i++) {            int a = scanner.nextInt();            int b = scanner.nextInt();            g.get(a).add(b);            g.get(b).add(a);        }                // If there is insufficient horse feed to feed the horses in the starting square, output "0 0"        if (m < w[1]) {            System.out.println("0 0");        } else {            // Otherwise, perform breadth-first search (BFS)            bfs();            // Output the result            System.out.println(res + " " + minv);        }    }}

2,21,15,0 0,60,6 7,0

1

2,20,00,0 0,00,0 0,0

3

import java.util.*;public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);                String[] s = sc.nextLine().trim().split(",");        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);        s = sc.nextLine().trim().split(",");        int sx = Integer.parseInt(s[0]), sy = Integer.parseInt(s[1]);        int[][] h = new int[n][m], o = new int[n][m];        s = sc.nextLine().trim().replace(" ", ",").split(",");        for (int i = 0, idx = 0; i < n; i++) {            for (int j = 0; j < m; j++) {                h[i][j] = Integer.parseInt(s[idx++]);            }        }        s = sc.nextLine().trim().replace(" ", ",").split(",");        for (int i = 0, idx = 0; i < n; i++) {            for (int j = 0; j < m; j++) {                o[i][j] = Integer.parseInt(s[idx++]);            }        }        // State record        Map<Integer, Set<Integer>> map = new HashMap<>();        for (int i = 0; i < n; i++) {            for (int j = 0; j < m; j++) {                map.put(i * m + j, new HashSet<>()); // For each point, open a set to record the speeds that have appeared            }        }        Queue<int[]> q = new LinkedList<>(); // Open queue        map.get(sx * m + sy).add(1);        q.offer(new int[]{sx, sy, 1}); // Initial point enters the queue (x, y, v)        int cnt = 0;        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};        while (!q.isEmpty()) {            int[] t = q.poll();            int x = t[0], y = t[1], v = t[2];            for (int i = 0; i < 4; i++) {                int a = x + dx[i], b = y + dy[i];                if (a < 0 || a >= n || b < 0 || b >= m) continue; // Classic BFS operation                int nv = v + h[x][y] - h[a][b] - o[a][b]; // Calculate speed                if (nv <= 0 || map.get(a * m + b).contains(nv)) continue; // Skip if (x, y, v) has been recorded or v <= 0                                if (nv == 1) cnt++; // If (x, y, 1) occurs for the first time, the answer is incremented by 1                map.get(a * m + b).add(nv); // Update map to store each (x, y, v)                q.offer(new int[]{a, b, nv}); // Classic BFS operation            }        }        System.out.println(cnt);    }}