BFS（廣度優先搜尋）

# Detailed analysis of BFS with adjacency list
def bfs_analysis(graph, start):
    queue = deque([start])        # O(1)
    visited = {start}             # O(1)

    while queue:                  # Executes at most V times
        vertex = queue.popleft()  # O(1) - each vertex dequeued once

        # This inner loop runs exactly deg(vertex) times
        for neighbor in graph[vertex]:  # Total across all vertices = E
            if neighbor not in visited:  # O(1) with set
                visited.add(neighbor)    # O(1) - each vertex added once
                queue.append(neighbor)   # O(1) - each vertex enqueued once

    # Analysis:
    # - Outer while loop: O(V) iterations
    # - Inner for loop: Sum of deg(v) for all v = 2E (undirected) or E (directed)
    # - Each operation inside: O(1)
    # Total: O(V + E)

# python
# LC 102 - Binary Tree Level Order Traversal
# IDEA: freeze len(queue) = size of the current level, pop exactly that many, enqueue their children
# time = O(n), space = O(w)   w = the widest level
from collections import deque

def levelOrder(root):
    if not root:
        return []
    levels = []
    queue = deque([root])
    while queue:
        level_size = len(queue)              # the whole current level, and nothing else
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(current_level)
    return levels

// java
// LC 102 - Binary Tree Level Order Traversal
// IDEA: freeze queue.size() = size of the current level, poll exactly that many
// time = O(n), space = O(w)
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) {
        return levels;
    }
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();        // read once: the queue grows inside the loop
        List<Integer> currentLevel = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        levels.add(currentLevel);
    }
    return levels;
}

root = [3,9,20,null,null,15,7]
queue [3]        level_size=1  pop 3, push 9 20      levels [[3]]
queue [9,20]     level_size=2  pop 9; pop 20, push 15 7   levels [[3],[9,20]]
queue [15,7]     level_size=2  pop 15; pop 7          levels [[3],[9,20],[15,7]]

# python
# LC 1971 - Find if Path Exists in Graph
# IDEA: BFS from source; dist doubles as the visited set and is written when a node is enqueued
# time = O(V + E), space = O(V + E)
from collections import deque

def validPath(n, edges, source, destination):
    graph = [[] for _ in range(n)]
    for u, v in edges:                       # undirected: both directions
        graph[u].append(v)
        graph[v].append(u)
    dist = {source: 0}                       # first arrival = shortest distance
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == destination:
            return True                      # dist[node] is the shortest path length
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1   # mark BEFORE enqueue
                queue.append(nxt)
    return False

// java
// LC 1971 - Find if Path Exists in Graph
// IDEA: BFS from source; dist[] doubles as the visited set and is written when a node is enqueued
// time = O(V + E), space = O(V + E)
public boolean validPath(int n, int[][] edges, int source, int destination) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] e : edges) {                  // undirected: both directions
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }
    int[] dist = new int[n];
    Arrays.fill(dist, -1);                   // -1 = not reached yet
    dist[source] = 0;
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(source);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (node == destination) {
            return true;
        }
        for (int nxt : graph.get(node)) {
            if (dist[nxt] == -1) {
                dist[nxt] = dist[node] + 1;  // mark BEFORE enqueue
                queue.offer(nxt);
            }
        }
    }
    return false;
}

Cells A and B are both in the current layer; X is a fresh neighbour of both.

mark on DEQUEUE (wrong)                    mark on ENQUEUE (right)
1. pop A -> X unmarked -> enqueue X        1. pop A -> X unmarked -> mark X, enqueue X
2. pop B -> X STILL unmarked -> enqueue X  2. pop B -> X marked -> skip
3. pop X -> mark, fresh -= 1               3. pop X -> fresh -= 1 happened once, at step 1
4. pop X again -> fresh -= 1 AGAIN

# python
# IDEA: parent[nxt] = node when nxt is first enqueued; walk parents back from the target
# time = O(V + E), space = O(V)
from collections import deque

def shortest_path(graph, start, target):
    parent = {start: None}                   # doubles as the visited set
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == target:
            path = []
            while node is not None:          # walk back to the start
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return []

# python
# LC 1091 - Shortest Path in Binary Matrix
# IDEA: BFS over cells; dirs = the 8 moves; the grid doubles as the visited set
# time = O(n^2), space = O(n^2)
from collections import deque

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    queue = deque([(0, 0, 1)])               # (row, col, cells on the path so far)
    grid[0][0] = 1                           # mark the start before the loop
    while queue:
        r, c, dist = queue.popleft()
        if r == n - 1 and c == n - 1:
            return dist
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                grid[nr][nc] = 1             # mark when enqueued
                queue.append((nr, nc, dist + 1))
    return -1

// java
// LC 1091 - Shortest Path in Binary Matrix
// IDEA: BFS over cells; dirs = the 8 moves; the grid doubles as the visited set
// time = O(n^2), space = O(n^2)
public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
        return -1;
    }
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
    Deque<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[]{0, 0, 1});
    grid[0][0] = 1;                          // mark visited
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int r = curr[0], c = curr[1], dist = curr[2];
        if (r == n - 1 && c == n - 1) {
            return dist;
        }
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                grid[nr][nc] = 1;            // mark when enqueued
                queue.offer(new int[]{nr, nc, dist + 1});
            }
        }
    }
    return -1;
}

# python
# LC 994 - Rotting Oranges
# IDEA: seed every rotten orange at minute 0; one BFS level = one minute; count fresh to detect -1
# time = O(m * n), space = O(m * n)
from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))         # every source at level 0
            elif grid[r][c] == 1:
                fresh += 1
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    minutes = 0
    while queue and fresh > 0:               # stop as soon as nothing is left to rot
        minutes += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2         # rot it when enqueued, not when popped
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

// java
// LC 994 - Rotting Oranges
// IDEA: seed every rotten orange at minute 0; one BFS level = one minute
// time = O(m * n), space = O(m * n)
public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Deque<int[]> queue = new ArrayDeque<>();
    int fresh = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) {
                queue.offer(new int[]{r, c});
            } else if (grid[r][c] == 1) {
                fresh++;
            }
        }
    }
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    int minutes = 0;
    while (!queue.isEmpty() && fresh > 0) {
        minutes++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;        // rot it when enqueued
                    fresh--;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}

grid = [[2,1,1],
        [1,1,0],
        [0,1,1]]          fresh = 6, queue = [(0,0)]
minute 1: rot (0,1) (1,0)          fresh 4
minute 2: rot (0,2) (1,1)          fresh 2
minute 3: rot (2,1)                fresh 1
minute 4: rot (2,2)                fresh 0  -> loop stops, answer 4

# python
# LC 542 - 01 Matrix
# IDEA: multi-source BFS from every 0; the first time a cell is reached sets its distance
# time = O(m * n), space = O(m * n)
from collections import deque

def updateMatrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]   # -1 = not reached yet
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        r, c = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist

// java
// LC 542 - 01 Matrix
// IDEA: Multi-source BFS — enqueue all 0s first, then expand
// time = O(M*N), space = O(M*N)
public int[][] updateMatrix(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[][] dist = new int[m][n];
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == 0) queue.offer(new int[]{i, j});
            else dist[i][j] = Integer.MAX_VALUE;
        }
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] d : dirs) {
            int nr = cell[0]+d[0], nc = cell[1]+d[1];
            if (nr>=0 && nr<m && nc>=0 && nc<n && dist[nr][nc] > dist[cell[0]][cell[1]]+1) {
                dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
    return dist;
}

# python
# LC 127 - Word Ladder
# IDEA: BFS over words; neighbours = every one-letter change that is in the dictionary
# time = O(N * 26 * L^2), space = O(N * L)   N = words, L = word length
from collections import deque

def ladderLength(beginWord, endWord, wordList):
    words = set(wordList)
    if endWord not in words:
        return 0
    visited = {beginWord}
    queue = deque([beginWord])
    steps = 1                                # beginWord itself is the first word
    while queue:
        for _ in range(len(queue)):
            word = queue.popleft()
            if word == endWord:
                return steps
            for i in range(len(word)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    if ch == word[i]:
                        continue
                    candidate = word[:i] + ch + word[i + 1:]
                    if candidate in words and candidate not in visited:
                        visited.add(candidate)          # mark when enqueued
                        queue.append(candidate)
        steps += 1
    return 0

// java
// LC 127 - Word Ladder
// IDEA: BFS over words; change one char in place, test the dictionary, then restore the char
// time = O(N * 26 * L^2), space = O(N * L)
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) {
        return 0;
    }
    Set<String> visited = new HashSet<>();
    Deque<String> queue = new ArrayDeque<>();
    queue.offer(beginWord);
    visited.add(beginWord);
    int steps = 1;                           // beginWord counts as the first word
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String cur = queue.poll();
            if (cur.equals(endWord)) {
                return steps;
            }
            char[] arr = cur.toCharArray();
            for (int j = 0; j < arr.length; j++) {
                char original = arr[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) {
                        continue;
                    }
                    arr[j] = c;              // try every letter at position j
                    String next = new String(arr);
                    if (dict.contains(next) && !visited.contains(next)) {
                        visited.add(next);   // mark BEFORE enqueue
                        queue.offer(next);
                    }
                }
                arr[j] = original;           // restore before moving to position j + 1
            }
        }
        steps++;
    }
    return 0;
}

# python
# LC 863 - All Nodes Distance K in Binary Tree
# IDEA: DFS build {node: parent}, then BFS "radiate outward" from target
# time = O(n), space = O(n)   each node is parented once and enqueued at most once
import collections

class Solution(object):
    def distanceK(self, root, target, k):
        # Step 1: map every node to its parent (the missing "up" edge)
        parents = {}
        def add_parents(node, parent):
            if not node:
                return
            parents[node] = parent
            add_parents(node.left, node)
            add_parents(node.right, node)
        add_parents(root, None)

        # Step 2: BFS outward from target
        queue = collections.deque([(target, 0)])   # (current_node, distance)
        visited = set([target])                    # MUST have: graph is undirected now
        ans = []

        while queue:
            node, dist = queue.popleft()

            if dist == k:
                ans.append(node.val)
                continue                            # don't expand past k

            # 3 directions: down-left, down-right, UP (parent)
            for neighbor in (node.left, node.right, parents[node]):
                if neighbor and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))

        return ans

// java
// LC 863 - All Nodes Distance K in Binary Tree
// IDEA: DFS build parent map, then BFS k steps out from target
// time = O(n), space = O(n)
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, TreeNode> parents = new HashMap<>();
    buildParents(root, null, parents);

    Deque<Object[]> queue = new ArrayDeque<>();
    queue.offer(new Object[]{target, 0});
    Set<TreeNode> visited = new HashSet<>();
    visited.add(target);
    List<Integer> ans = new ArrayList<>();

    while (!queue.isEmpty()) {
        Object[] cur = queue.poll();
        TreeNode node = (TreeNode) cur[0];
        int dist = (int) cur[1];

        if (dist == k) {          // exactly k edges away
            ans.add(node.val);
            continue;             // stop expanding this branch
        }
        for (TreeNode nei : new TreeNode[]{node.left, node.right, parents.get(node)}) {
            if (nei != null && visited.add(nei)) {   // add() returns false if seen
                queue.offer(new Object[]{nei, dist + 1});
            }
        }
    }
    return ans;
}

private void buildParents(TreeNode node, TreeNode parent, Map<TreeNode, TreeNode> parents) {
    if (node == null) return;
    parents.put(node, parent);
    buildParents(node.left, node, parents);
    buildParents(node.right, node, parents);
}

        3                  BFS from 5 (each layer = distance):
      /   \                dist 0 : 5
     5     1               dist 1 : 6, 2  (children) , 3  (PARENT ← the key edge)
    / \   / \              dist 2 : 7, 4  (via 2)    , 1  (via 3, sibling subtree)
   6   2 0   8                      ^^^^^^^^^^^^^^^^^^^^^ answer = [7, 4, 1]
      / \
     7   4              Without the parent edge you would only find 7 and 4 — the
                        node `1` requires going UP to 3, then DOWN to 1.

# python
# LC 863 - All Nodes Distance K in Binary Tree (k level expansions)
# IDEA: no distance stored; after exactly k level expansions the queue IS the answer set
# time = O(n), space = O(n)
import collections

class Solution(object):
    def distanceK(self, root, target, k):
        parents = {}
        def add_parents(node, parent):
            if not node:
                return
            parents[node] = parent
            add_parents(node.left, node)
            add_parents(node.right, node)
        add_parents(root, None)

        q = collections.deque([target])
        visited = {target}
        for _ in range(k):                     # k full level expansions
            for _ in range(len(q)):            # snapshot the level size FIRST
                node = q.popleft()
                for nxt in (node.left, node.right, parents[node]):
                    if nxt and nxt not in visited:
                        visited.add(nxt)
                        q.append(nxt)
        return [node.val for node in q]        # everything left is exactly k away