BFS 与 DFS：图论算法的基础

void dfs(TreeNode u) {
    if (u == null) return;
    // 前序位置：进入节点时
    dfs(u.left);
    // 中序位置
    dfs(u.right);
    // 后序位置：离开节点时（子树信息已齐全）
}

void dfs(int u, boolean[] visited) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) dfs(v, visited);
    }
}

Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{start, 0});      // {节点, 子节点遍历进度}
while (!stack.isEmpty()) {
    int[] top = stack.peek();
    int u = top[0], idx = top[1];
    if (idx == graph[u].length) {     // 子节点全部遍历完
        stack.pop();
        continue;
    }
    top[1]++;
    int v = graph[u][idx];
    if (!visited[v]) {
        visited[v] = true;
        stack.push(new int[]{v, 0});
    }
}

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>(sz);
        for (int i = 0; i < sz; i++) {
            TreeNode u = q.poll();
            level.add(u.val);
            if (u.left != null) q.offer(u.left);
            if (u.right != null) q.offer(u.right);
        }
        ans.add(level);
    }
    return ans;
}

int[] dist = new int[n];
Arrays.fill(dist, -1);
Deque<Integer> q = new ArrayDeque<>();
q.offer(start); dist[start] = 0;
while (!q.isEmpty()) {
    int u = q.poll();
    for (int v : graph[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.offer(v);
        }
    }
}

for (int i = 0; i < n; i++) if (grid[i] == 'O') q.offer(i);
// 之后正常 BFS

// 适用：扩展规则对称、状态可哈希（如单词接龙、字母变换）
int bidirectionalBFS(String s, String t, Set<String> dict) {
    if (s.equals(t)) return 0;
    Set<String> head = new HashSet<>(Set.of(s));
    Set<String> tail = new HashSet<>(Set.of(t));
    Set<String> visited = new HashSet<>();
    int step = 0;
    while (!head.isEmpty() && !tail.isEmpty()) {
        // 优化：每次扩展 size 较小的方向
        if (head.size() > tail.size()) {
            Set<String> tmp = head; head = tail; tail = tmp;
        }
        Set<String> next = new HashSet<>();
        for (String cur : head) {
            if (tail.contains(cur)) return step + 1;   // 相遇
            for (String nb : expand(cur, dict)) {
                if (!visited.contains(nb)) {
                    visited.add(nb);
                    next.add(nb);
                }
            }
        }
        head = next;
        step++;
    }
    return -1;
}

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
    ans.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, ans);
        path.remove(path.size() - 1);
    }
}

int[] in = new int[n];
for (int[] e : edges) in[e[1]]++;
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (in[i] == 0) q.offer(i);
while (!q.isEmpty()) {
    int u = q.poll(); order.add(u);
    for (int v : graph[u]) if (--in[v] == 0) q.offer(v);
}
// 检测环：order.size() == n ? 无环 : 有环

int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[s] = 0;

// ⚠️ 不要用 (a, b) -> a[1] - b[1]，会整数溢出
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{s, 0});
while (!pq.isEmpty()) {
    int[] top = pq.poll();
    int u = top[0], d = top[1];
    if (d > dist[u]) continue;     // 跳过过期条目
    for (int[] e : graph[u]) {
        int v = e[0], w = e[1];
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.offer(new int[]{v, dist[v]});
        }
    }
}