Представление графов и настройка обхода

Что такое граф?

# Graph terminology:
# - V: set of vertices (nodes)
# - E: set of edges
# - Directed graph: edges have direction (A -> B but not B -> A)
# - Undirected graph: edges are bidirectional
# - Weighted graph: edges have costs/weights
# - Cyclic: contains at least one cycle
# - Acyclic: no cycles (DAG = Directed Acyclic Graph)
# - Connected: every node reachable from every other
# - Disconnected: multiple isolated components
print('Graph: nodes + edges, directed/undirected, weighted/unweighted')

Представление в виде списка смежности

from collections import defaultdict

# Build an undirected graph
def build_undirected(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # both directions
    return graph

edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
graph = build_undirected(edges)
print(dict(graph))
# {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3]}

# Directed graph: only one direction
def build_directed(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)  # only u -> v
    return graph

Представление в виде матрицы смежности

# Adjacency matrix for 5 nodes
V = 5
matrix = [[0] * V for _ in range(V)]

edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1  # undirected

# Print the matrix:
for row in matrix:
    print(row)
# Neighbour check: O(1)
print('Edge 0-2:', bool(matrix[0][2]))  # True
print('Edge 0-4:', bool(matrix[0][4]))  # False

# Space: O(V^2) vs adjacency list O(V+E)
# Dense graph: matrix often better; sparse: list better

Представление в виде списка рёбер

# Weighted edge list: (source, destination, weight)
edge_list = [
    (0, 1, 4),
    (0, 2, 1),
    (1, 3, 1),
    (2, 3, 5),
    (3, 4, 3)
]

# Useful for:
# Bellman-Ford: iterate all edges n-1 times
# Kruskal's MST: sort by weight then union-find

# Sort by weight for Kruskal:
edge_list_sorted = sorted(edge_list, key=lambda e: e[2])
print('Sorted by weight:', edge_list_sorted)

# Finding neighbours: O(E) scan -- inefficient for traversal
node_0_neighbors = [v for u, v, w in edge_list if u == 0]
print('Node 0 neighbors:', node_0_neighbors)

Настройка BFS: очередь и множество посещённых вершин

from collections import deque

def bfs(graph, start):
    visited = {start}        # mark source as visited
    queue = deque([start])   # initialise queue
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)     # mark BEFORE enqueue
                queue.append(neighbour)
    return order

from collections import defaultdict
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(graph, 0))  # [0, 1, 2, 3, 4]

Настройка DFS: стек или рекурсия

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None: visited = set(); order = []
    visited.add(node)
    order.append(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited, order)
    return order

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):  # reverse for same order as recursive
            if neighbour not in visited:
                stack.append(neighbour)
    return order

print('Recursive DFS:', dfs_recursive(graph, 0))
print('Iterative DFS:', dfs_iterative(graph, 0))

Когда использовать BFS, а когда DFS

# BFS use cases:
# - Shortest path in unweighted graph (fewest edges)
# - Level-order traversal
# - Word ladder (minimum transformations)
# - Clone graph

# DFS use cases:
# - Connected components (flood fill)
# - Cycle detection
# - Topological sort
# - All paths between two nodes
# - Maze solving (any path)
# - N-queens, Sudoku (backtracking)

# Both: O(V + E) time, O(V) space for visited
print('BFS: shortest hops | DFS: existence and enumeration')

Граф из форматов входных данных LeetCode

# Format 1: edge list -> adjacency list
def edges_to_adj(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph

# Format 2: 2D grid -> adjacency (implicit)
# Neighbours of (r, c): (r-1,c), (r+1,c), (r,c-1), (r,c+1)
DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
def grid_neighbours(grid, r, c):
    rows, cols = len(grid), len(grid[0])
    return [(r+dr, c+dc) for dr, dc in DIRS
            if 0 <= r+dr < rows and 0 <= c+dc < cols]

grid = [[1,1,0],[0,1,1],[1,0,0]]
print('Neighbours of (0,0):', grid_neighbours(grid, 0, 0))
print('Neighbours of (1,1):', grid_neighbours(grid, 1, 1))

Пометка посещённых ячеек в сетках

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '#'  # mark as visited (in-place)
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

grid = [['1','1','0','0'],
        ['1','1','0','0'],
        ['0','0','1','0'],
        ['0','0','0','1']]
print(num_islands(grid))  # 3

Инициализация BFS из нескольких источников

from collections import deque

def rotting_oranges(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Multi-source: all rotten oranges start at time=0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh += 1
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    time = 0
    while queue:
        r, c, t = 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  # mark rotten
                fresh -= 1
                queue.append((nr, nc, t+1))
                time = t + 1
    return time if fresh == 0 else -1

print(rotting_oranges([[2,1,1],[1,1,0],[0,1,1]]))  # 4

Плотность графа и выбор представления

# Graph density comparison:
# Sparse: social network (V=1B users, avg 200 friends)
#   E = 200 * 1B = 200B << V^2 = 10^18 -> adjacency list
# Dense: complete graph (every node connected to every other)
#   E = V*(V-1)/2 ≈ V^2 -> adjacency matrix

# Interview rule of thumb:
# - Default to adjacency list (defaultdict(list))
# - Use matrix only when asked about dense graph or O(1) edge lookup
# - Grid problems: use implicit adjacency (4-directional neighbours)

print('Sparse graph (E << V^2): use adjacency list')
print('Dense graph (E ~ V^2): consider adjacency matrix')

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

Итоги урока