BFS: кратчайший путь и обход по уровням

BFS и кратчайший путь в невзвешенных графах

from collections import deque, defaultdict

def shortest_path(graph, start, end):
    if start == end:
        return 0
    visited = {start}
    queue = deque([(start, 0)])  # (node, distance)
    while queue:
        node, dist = queue.popleft()
        for neighbour in graph[node]:
            if neighbour == end:
                return dist + 1
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append((neighbour, dist + 1))
    return -1  # no path found

graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(0,3),(1,4)]:
    graph[u].append(v); graph[v].append(u)
print(shortest_path(graph, 0, 3))  # 1 (direct edge)
print(shortest_path(graph, 0, 4))  # 2 (0->1->4)

Отслеживание фактического кратчайшего пути

from collections import deque, defaultdict

def shortest_path_with_route(graph, start, end):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == end:
            break
        for nb in graph[node]:
            if nb not in parent:
                parent[nb] = node
                queue.append(nb)
    if end not in parent:
        return []  # no path
    # Reconstruct path by tracing back
    path = []
    node = end
    while node is not None:
        path.append(node)
        node = parent[node]
    return path[::-1]  # reverse

graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(0,4),(4,3)]:
    graph[u].append(v); graph[v].append(u)
print(shortest_path_with_route(graph, 0, 3))  # [0, 4, 3] or [0, 1, 2, 3]

Лестница слов: BFS на неявном графе

from collections import deque

def word_ladder(begin_word, end_word, word_list):
    word_set = set(word_list)
    if end_word not in word_set:
        return 0
    queue = deque([(begin_word, 1)])
    visited = {begin_word}
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                if new_word == end_word:
                    return steps + 1
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))
    return 0

print(word_ladder('hit', 'cog', ['hot','dot','dog','lot','log','cog']))  # 5

Обход по уровням: отслеживание расстояния

from collections import deque, defaultdict

def bfs_levels(graph, start):
    levels = {}
    visited = {start}
    queue = deque([start])
    dist = 0
    while queue:
        # Process all nodes at current distance
        for _ in range(len(queue)):
            node = queue.popleft()
            levels[node] = dist
            for nb in graph[node]:
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        dist += 1
    return levels

graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,3),(2,3),(3,4)]:
    graph[u].append(v); graph[v].append(u)
print(bfs_levels(graph, 0))  # {0:0, 1:1, 2:1, 3:2, 4:3}

Клонирование графа

from collections import deque

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    if not node:
        return None
    old_to_new = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        curr = queue.popleft()
        for nb in curr.neighbors:
            if nb not in old_to_new:
                old_to_new[nb] = Node(nb.val)
                queue.append(nb)
            old_to_new[curr].neighbors.append(old_to_new[nb])
    return old_to_new[node]

# Build a simple graph: 1 -- 2 -- 3 -- 4 -- 1
n1 = Node(1); n2 = Node(2); n3 = Node(3); n4 = Node(4)
n1.neighbors = [n2, n4]; n2.neighbors = [n1, n3]
n3.neighbors = [n2, n4]; n4.neighbors = [n3, n1]
cloned = clone_graph(n1)
print(cloned.val, [n.val for n in cloned.neighbors])  # 1 [2, 4]

Двунаправленный BFS

from collections import defaultdict

def word_ladder_bidir(begin, end, word_list):
    word_set = set(word_list)
    if end not in word_set:
        return 0
    front, back = {begin}, {end}
    visited = {begin, end}
    steps = 1
    while front and back:
        # Always expand the smaller frontier
        if len(front) > len(back):
            front, back = back, front
        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    nw = word[:i] + c + word[i+1:]
                    if nw in back:  # frontiers met!
                        return steps + 1
                    if nw in word_set and nw not in visited:
                        visited.add(nw)
                        next_front.add(nw)
        front = next_front
        steps += 1
    return 0

print(word_ladder_bidir('hit','cog',['hot','dot','dog','lot','log','cog']))  # 5

BFS 0–1 для взвешенных графов

from collections import deque

def zero_one_bfs(graph, start, n):
    # graph: list of (neighbour, weight) where weight is 0 or 1
    dist = [float('inf')] * n
    dist[start] = 0
    dq = deque([start])
    while dq:
        node = dq.popleft()
        for nb, w in graph[node]:
            if dist[node] + w < dist[nb]:
                dist[nb] = dist[node] + w
                if w == 0:
                    dq.appendleft(nb)   # same level
                else:
                    dq.append(nb)       # next level
    return dist

# Simple test:
graph = [[(1, 0), (2, 1)],   # node 0: free to 1, cost 1 to 2
         [(3, 1)],            # node 1: cost 1 to 3
         [(3, 0)],            # node 2: free to 3
         []]
print(zero_one_bfs(graph, 0, 4))  # [0, 0, 1, 1]

Стены и ворота (BFS из нескольких источников)

from collections import deque

def walls_and_gates(rooms):
    if not rooms:
        return
    rows, cols = len(rooms), len(rooms[0])
    INF = float('inf')
    queue = deque()
    # Multi-source: all gates at distance 0
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:  # gate
                queue.append((r, c))
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    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 rooms[nr][nc]==INF:
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

rooms = [[float('inf'),-1,0,float('inf')],
         [float('inf'),float('inf'),float('inf'),-1],
         [float('inf'),-1,float('inf'),-1],
         [0,-1,float('inf'),float('inf')]]
walls_and_gates(rooms)
print(rooms[0][0], rooms[1][1])  # 3, 2

BFS для игры «Змеи и лестницы»

from collections import deque

def snakes_and_ladders(board):
    n = len(board)
    def get_board(pos):
        r, c = divmod(pos - 1, n)
        if r % 2 == 1: c = n - 1 - c  # alternating direction
        return board[n - 1 - r][c]

    visited = {1}
    queue = deque([(1, 0)])
    while queue:
        pos, moves = queue.popleft()
        for dice in range(1, 7):
            next_pos = pos + dice
            if next_pos > n * n:
                break
            val = get_board(next_pos)
            if val != -1:
                next_pos = val  # snake or ladder
            if next_pos == n * n:
                return moves + 1
            if next_pos not in visited:
                visited.add(next_pos)
                queue.append((next_pos, moves + 1))
    return -1

print('BFS models game as an unweighted shortest-path problem')

Сложность и оптимизация BFS

# BFS on a graph with V vertices and E edges:
# Time:  O(V + E) -- each vertex and edge visited once
# Space: O(V)     -- visited set + queue

# BFS on an m x n grid:
# V = m*n cells
# E <= 4*m*n edges (4 directions, max)
# Time:  O(m*n)
# Space: O(m*n)

# Common pitfalls:
# 1. Marking visited on dequeue (not enqueue) -> same node queued multiple times
# 2. Using a list for visited -> O(n) membership check -> O(V*E) total
# 3. Not handling disconnected graph -> BFS from single source misses components
print('O(V+E) time, O(V) space -- mark visited on enqueue')

Ближайший 0 в двоичной матрице

from collections import deque

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    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 = [(0,1),(0,-1),(1,0),(-1,0)]
    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:
                if dist[r][c] + 1 < dist[nr][nc]:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
    return dist

mat = [[0,0,0],[0,1,0],[1,1,1]]
result = update_matrix(mat)
for row in result: print(row)  # [[0,0,0],[0,1,0],[1,2,1]]

Быстрая проверка

Итоги урока