BFS Applications — Shortest Path (Unweighted) and Beyond

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

from collections import deque
from typing import Dict, List, Optional, Tuple, Set
 
class ShortestPathResult:
    """Result of BFS shortest path computation."""
    def __init__(self):
        self.distance: Dict[int, int] = {}
        self.parent: Dict[int, Optional[int]] = {}
        self.reachable: Set[int] = set()
 
def bfs_shortest_paths(
    graph: Dict[int, List[int]], 
    source: int
) -> ShortestPathResult:
    """
    Compute shortest paths from source to all reachable vertices.
    
    Returns a ShortestPathResult containing:
    - distance: dict mapping vertex to its distance from source
    - parent: dict mapping vertex to its predecessor on shortest path
    - reachable: set of all vertices reachable from source
    """
    result = ShortestPathResult()
    result.distance[source] = 0
    result.parent[source] = None
    result.reachable.add(source)
    
    queue: deque = deque([source])
    
    while queue:
        u = queue.popleft()
        
        for v in graph.get(u, []):
            if v not in result.reachable:
                result.reachable.add(v)
                result.distance[v] = result.distance[u] + 1
                result.parent[v] = u
                queue.append(v)
    
    return result
 
 
def reconstruct_path(result: ShortestPathResult, target: int) -> Optional[List[int]]:
    """
    Reconstruct the shortest path from source to target.
    
    Returns None if target is unreachable.
    """
    if target not in result.reachable:
        return None
    
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = result.parent[current]
    
    return path[::-1]  # Reverse to get source-to-target order
 
 
def shortest_path_point_to_point(
    graph: Dict[int, List[int]], 
    source: int, 
    target: int
) -> Tuple[int, Optional[List[int]]]:
    """
    Find shortest path from source to target with early termination.
    
    Optimization: Stop BFS as soon as we reach the target.
    
    Returns (distance, path) or (-1, None) if unreachable.
    """
    if source == target:
        return (0, [source])
    
    visited: Set[int] = {source}
    parent: Dict[int, Optional[int]] = {source: None}
    queue: deque = deque([source])
    
    while queue:
        u = queue.popleft()
        
        for v in graph.get(u, []):
            if v not in visited:
                visited.add(v)
                parent[v] = u
                
                # Early termination when target is found
                if v == target:
                    # Reconstruct path
                    path = []
                    current = v
                    while current is not None:
                        path.append(current)
                        current = parent[current]
                    return (len(path) - 1, path[::-1])
                
                queue.append(v)
    
    return (-1, None)  # Target unreachable
 
 
# Example: Finding shortest path in a maze
def shortest_path_maze(
    maze: List[List[int]], 
    start: Tuple[int, int], 
    end: Tuple[int, int]
) -> int:
    """
    Find shortest path in a maze from start to end.
    
    0 = passable, 1 = wall
    Returns number of steps, or -1 if impossible.
    """
    rows, cols = len(maze), len(maze[0])
    sr, sc = start
    er, ec = end
    
    if maze[sr][sc] == 1 or maze[er][ec] == 1:
        return -1
    
    visited = [[False] * cols for _ in range(rows)]
    visited[sr][sc] = True
    queue: deque = deque([(sr, sc, 0)])
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        r, c, dist = queue.popleft()
        
        if (r, c) == end:
            return dist
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if (0 <= nr < rows and 0 <= nc < cols and 
                not visited[nr][nc] and maze[nr][nc] == 0):
                visited[nr][nc] = True
                queue.append((nr, nc, dist + 1))
    
    return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

from collections import deque
from typing import Dict, List, Set, Tuple
 
def find_connected_components(
    graph: Dict[int, List[int]], 
    vertices: Set[int]
) -> Tuple[int, Dict[int, int]]:
    """
    Find all connected components in an undirected graph.
    
    Args:
        graph: Adjacency list representation
        vertices: Set of all vertices in the graph
    
    Returns:
        (num_components, component_assignment)
        where component_assignment maps each vertex to its component ID (0-indexed)
    """
    component: Dict[int, int] = {}
    component_id = 0
    
    for start_vertex in vertices:
        if start_vertex in component:
            continue  # Already assigned to a component
        
        # BFS to discover all vertices in this component
        queue: deque = deque([start_vertex])
        component[start_vertex] = component_id
        
        while queue:
            u = queue.popleft()
            
            for v in graph.get(u, []):
                if v not in component:
                    component[v] = component_id
                    queue.append(v)
        
        component_id += 1
    
    return (component_id, component)
 
 
def count_islands(grid: List[List[str]]) -> int:
    """
    Count number of islands in a grid.
    
    '1' = land, '0' = water
    Islands are formed by connecting adjacent (4-directionally) land cells.
    
    This is connected components on a grid!
    """
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    island_count = 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    def bfs_flood(start_r: int, start_c: int):
        """BFS to mark all cells of an island."""
        queue: deque = deque([(start_r, start_c)])
        visited[start_r][start_c] = True
        
        while queue:
            r, c = queue.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                if (0 <= nr < rows and 0 <= nc < cols and 
                    not visited[nr][nc] and grid[nr][nc] == '1'):
                    visited[nr][nc] = True
                    queue.append((nr, nc))
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and not visited[r][c]:
                bfs_flood(r, c)
                island_count += 1
    
    return island_count
 
 
def largest_component_size(graph: Dict[int, List[int]], vertices: Set[int]) -> int:
    """
    Find the size of the largest connected component.
    
    Uses BFS with component size tracking.
    """
    visited: Set[int] = set()
    max_size = 0
    
    for start_vertex in vertices:
        if start_vertex in visited:
            continue
        
        # BFS to count component size
        queue: deque = deque([start_vertex])
        visited.add(start_vertex)
        component_size = 0
        
        while queue:
            u = queue.popleft()
            component_size += 1
            
            for v in graph.get(u, []):
                if v not in visited:
                    visited.add(v)
                    queue.append(v)
        
        max_size = max(max_size, component_size)
    
    return max_size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

from collections import deque
from typing import Dict, List, Set, Tuple, Optional
 
def is_bipartite(graph: Dict[int, List[int]], vertices: Set[int]) -> bool:
    """
    Check if the graph is bipartite using BFS two-coloring.
    
    Handles disconnected graphs by checking all components.
    
    Returns True if bipartite, False otherwise.
    """
    # Color assignment: 0 or 1, -1 means uncolored
    color: Dict[int, int] = {}
    
    for start_vertex in vertices:
        if start_vertex in color:
            continue  # Already colored in a previous component
        
        # BFS coloring for this component
        queue: deque = deque([start_vertex])
        color[start_vertex] = 0
        
        while queue:
            u = queue.popleft()
            
            for v in graph.get(u, []):
                if v not in color:
                    # Assign opposite color
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    # Adjacent vertices have same color → not bipartite
                    return False
    
    return True
 
 
def get_bipartition(
    graph: Dict[int, List[int]], 
    vertices: Set[int]
) -> Optional[Tuple[Set[int], Set[int]]]:
    """
    If bipartite, return the two sets of vertices.
    If not bipartite, return None.
    """
    color: Dict[int, int] = {}
    
    for start_vertex in vertices:
        if start_vertex in color:
            continue
        
        queue: deque = deque([start_vertex])
        color[start_vertex] = 0
        
        while queue:
            u = queue.popleft()
            
            for v in graph.get(u, []):
                if v not in color:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return None
    
    set_a = {v for v, c in color.items() if c == 0}
    set_b = {v for v, c in color.items() if c == 1}
    
    return (set_a, set_b)
 
 
def is_bipartite_graph(graph: List[List[int]]) -> bool:
    """
    LeetCode-style: Check if graph (0-indexed adjacency list) is bipartite.
    """
    n = len(graph)
    color = [-1] * n  # -1 = uncolored
    
    for start in range(n):
        if color[start] != -1:
            continue
        
        queue: deque = deque([start])
        color[start] = 0
        
        while queue:
            u = queue.popleft()
            
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False
    
    return True
 
 
def possible_bipartition(n: int, dislikes: List[List[int]]) -> bool:
    """
    Can n people be split into two groups such that no two people 
    in the same group dislike each other?
    
    Model as graph: people are vertices, dislikes are edges.
    Check if this graph is bipartite.
    
    This is the "Possible Bipartition" problem on LeetCode.
    """
    # Build adjacency list from dislikes
    graph: List[List[int]] = [[] for _ in range(n + 1)]
    for a, b in dislikes:
        graph[a].append(b)
        graph[b].append(a)
    
    color = [-1] * (n + 1)
    
    for person in range(1, n + 1):
        if color[person] != -1:
            continue
        
        queue: deque = deque([person])
        color[person] = 0
        
        while queue:
            u = queue.popleft()
            
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False
    
    return True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

from collections import deque
from typing import List, Set, Tuple, Optional
 
def sliding_puzzle(board: List[List[int]]) -> int:
    """
    Solve the sliding puzzle (2x3 version).
    
    Board contains digits 1-5 and 0 (empty space).
    Goal: reach the state [[1,2,3],[4,5,0]]
    
    Returns minimum moves, or -1 if unsolvable.
    
    State: tuple representation of board
    Transitions: swap 0 with an adjacent cell
    """
    # Convert board to tuple (hashable state representation)
    def board_to_tuple(b: List[List[int]]) -> Tuple[int, ...]:
        return tuple(b[0] + b[1])
    
    def find_zero(state: Tuple[int, ...]) -> int:
        return state.index(0)
    
    # Valid moves: which positions can swap with each position
    # For 2x3 board with positions 0-5:
    #   0 1 2
    #   3 4 5
    neighbors = {
        0: [1, 3],
        1: [0, 2, 4],
        2: [1, 5],
        3: [0, 4],
        4: [1, 3, 5],
        5: [2, 4]
    }
    
    initial = board_to_tuple(board)
    goal = (1, 2, 3, 4, 5, 0)
    
    if initial == goal:
        return 0
    
    visited: Set[Tuple[int, ...]] = {initial}
    queue: deque = deque([(initial, 0)])  # (state, moves)
    
    while queue:
        state, moves = queue.popleft()
        zero_pos = find_zero(state)
        
        for neighbor_pos in neighbors[zero_pos]:
            # Swap zero with neighbor
            state_list = list(state)
            state_list[zero_pos], state_list[neighbor_pos] = \
                state_list[neighbor_pos], state_list[zero_pos]
            new_state = tuple(state_list)
            
            if new_state == goal:
                return moves + 1
            
            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, moves + 1))
    
    return -1  # Unsolvable
 
 
def open_lock(deadends: List[str], target: str) -> int:
    """
    Open a 4-digit lock by turning wheels.
    
    Start at "0000". Each move turns one wheel up or down by 1.
    Cannot visit any deadend configuration.
    Find minimum moves to reach target.
    
    State: 4-digit string
    Transitions: 8 possible (4 wheels × 2 directions)
    """
    dead_set = set(deadends)
    
    if "0000" in dead_set:
        return -1
    if target == "0000":
        return 0
    
    def get_neighbors(state: str) -> List[str]:
        """Generate all states reachable with one move."""
        result = []
        for i in range(4):
            digit = int(state[i])
            # Turn up
            up = (digit + 1) % 10
            result.append(state[:i] + str(up) + state[i+1:])
            # Turn down
            down = (digit - 1) % 10
            result.append(state[:i] + str(down) + state[i+1:])
        return result
    
    visited: Set[str] = {"0000"}
    queue: deque = deque([("0000", 0)])
    
    while queue:
        state, moves = queue.popleft()
        
        for neighbor in get_neighbors(state):
            if neighbor == target:
                return moves + 1
            
            if neighbor not in visited and neighbor not in dead_set:
                visited.add(neighbor)
                queue.append((neighbor, moves + 1))
    
    return -1
 
 
def minimum_genetic_mutation(
    startGene: str, 
    endGene: str, 
    bank: List[str]
) -> int:
    """
    Find minimum mutations to transform startGene to endGene.
    
    Each gene is an 8-character string of A, C, G, T.
    Each mutation changes exactly one character.
    All intermediate and final genes must be in the bank.
    
    This is exactly Word Ladder with a different character set!
    """
    bank_set = set(bank)
    
    if endGene not in bank_set:
        return -1
    
    visited: Set[str] = {startGene}
    queue: deque = deque([(startGene, 0)])
    
    while queue:
        gene, mutations = queue.popleft()
        
        if gene == endGene:
            return mutations
        
        # Try each possible single-character mutation
        for i in range(len(gene)):
            for c in "ACGT":
                if c == gene[i]:
                    continue
                
                mutated = gene[:i] + c + gene[i+1:]
                
                if mutated in bank_set and mutated not in visited:
                    visited.add(mutated)
                    queue.append((mutated, mutations + 1))
    
    return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

from collections import deque
from typing import Dict, List, Tuple, Set
 
def tree_diameter(adj: Dict[int, List[int]], n: int) -> int:
    """
    Find the diameter of a tree (longest path).
    
    Two-BFS approach:
    1. BFS from any node to find the farthest node
    2. BFS from that node to find the true farthest (diameter endpoint)
    """
    def bfs_farthest(start: int) -> Tuple[int, int]:
        """Return (farthest_node, distance_to_it)."""
        dist = {start: 0}
        queue: deque = deque([start])
        
        farthest = start
        max_dist = 0
        
        while queue:
            u = queue.popleft()
            
            if dist[u] > max_dist:
                max_dist = dist[u]
                farthest = u
            
            for v in adj.get(u, []):
                if v not in dist:
                    dist[v] = dist[u] + 1
                    queue.append(v)
        
        return (farthest, max_dist)
    
    # First BFS: find one endpoint of diameter
    endpoint1, _ = bfs_farthest(0)  # Start from any node
    
    # Second BFS: find the other endpoint and diameter
    endpoint2, diameter = bfs_farthest(endpoint1)
    
    return diameter
 
 
def flood_fill(
    image: List[List[int]], 
    sr: int, sc: int, 
    new_color: int
) -> List[List[int]]:
    """
    Flood fill from (sr, sc) with new_color.
    Replace all connected cells of the same color.
    
    Classic BFS on a grid.
    """
    rows, cols = len(image), len(image[0])
    original_color = image[sr][sc]
    
    # Edge case: already the target color
    if original_color == new_color:
        return image
    
    queue: deque = deque([(sr, sc)])
    image[sr][sc] = new_color
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if (0 <= nr < rows and 0 <= nc < cols and 
                image[nr][nc] == original_color):
                image[nr][nc] = new_color
                queue.append((nr, nc))
    
    return image
 
 
def nearest_zero_distance(matrix: List[List[int]]) -> List[List[int]]:
    """
    For each cell with value 1, find distance to nearest 0.
    Cells with 0 have distance 0.
    
    Multi-source BFS from all 0 cells simultaneously.
    """
    rows, cols = len(matrix), len(matrix[0])
    distance = [[float('inf')] * cols for _ in range(rows)]
    queue: deque = deque()
    
    # Initialize all 0 cells as sources
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                distance[r][c] = 0
                queue.append((r, c))
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if (0 <= nr < rows and 0 <= nc < cols and 
                distance[nr][nc] > distance[r][c] + 1):
                distance[nr][nc] = distance[r][c] + 1
                queue.append((nr, nc))
    
    return distance
 
 
def snakes_and_ladders(board: List[List[int]]) -> int:
    """
    Find minimum moves to reach the end of a Snakes and Ladders board.
    
    N×N board, squares numbered 1 to N².
    From square s, you can move to s+1 through s+6 (dice roll).
    Snakes/ladders instantly transport you.
    
    State: current square number
    Transitions: move to squares reachable by dice + snake/ladder
    """
    n = len(board)
    
    def get_position(s: int) -> Tuple[int, int]:
        """Convert square number to (row, col)."""
        s -= 1  # 0-indexed
        row = n - 1 - s // n
        col = s % n if (n - 1 - row) % 2 == 0 else n - 1 - s % n
        return (row, col)
    
    visited: Set[int] = {1}
    queue: deque = deque([(1, 0)])  # (square, moves)
    target = n * n
    
    while queue:
        square, moves = queue.popleft()
        
        # Try all dice rolls
        for dice in range(1, 7):
            next_square = square + dice
            
            if next_square > target:
                continue
            
            r, c = get_position(next_square)
            
            # Check for snake or ladder
            if board[r][c] != -1:
                next_square = board[r][c]
            
            if next_square == target:
                return moves + 1
            
            if next_square not in visited:
                visited.add(next_square)
                queue.append((next_square, moves + 1))
    
    return -1