Табличные и графовые модели
Две структуры, которыми описывают полмира задач: таблицы для отношений «каждый с каждым» и графы для связей.
Граф — модель из вершин (объектов) и рёбер (связей между ними); описывает сети любой природы — от дорог до социальных связей.
Зачем это нужно
Карта дорог, схема метро, расписание, социальная сеть, интернет — всё это графы. Таблицы стоимостей, матрицы расстояний, турнирные таблицы — это табличные модели. Эти две формы лежат в основе огромного числа задач: найти кратчайший путь, проверить связность, распределить ресурсы. На ЕГЭ графы и таблицы — стабильный блок заданий. Научимся представлять их в программе и работать с ними.
Почему именно графы оказались таким универсальным языком? Потому что огромное множество явлений в основе своей сводится к одному и тому же: есть объекты и есть связи между ними. Города и дороги, люди и знакомства, страницы и ссылки, задачи и зависимости, состояния игры и ходы — во всех этих случаях природа объектов разная, а структура одинаковая. И это даёт колоссальную экономию мысли: придумав один алгоритм поиска пути в графе, вы решаете им сразу и задачу о маршруте в навигаторе, и задачу о «рукопожатиях» в соцсети, и задачу о том, можно ли пройти лабиринт. Графовое мышление — это умение разглядеть за конкретной задачей абстрактную структуру «вершины и рёбра» и применить к ней уже готовые приёмы. Таблицы дополняют картину для случаев, когда важны отношения между каждой парой объектов. Вместе они образуют фундамент дискретного моделирования, и именно его основы мы здесь заложим.
Табличная модель: матрица расстояний
Таблица удобна, когда нужно описать отношение между каждой парой объектов. Классика — таблица (матрица) расстояний между городами. В программе это список списков. Найдём по такой таблице самую дальнюю пару городов:
cities = ["Москва", "Тула", "Орёл", "Курск"]
# симметричная матрица расстояний (км), 0 на диагонали
dist = [
[0, 180, 360, 540],
[180, 0, 180, 360],
[360, 180, 0, 180],
[540, 360, 180, 0],
]
max_d = 0
pair = None
for i in range(len(cities)):
for j in range(i + 1, len(cities)):
if dist[i][j] > max_d:
max_d = dist[i][j]
pair = (cities[i], cities[j])
print("самая дальняя пара:", pair, "—", max_d, "км")
print("расстояние Тула–Курск:", dist[1][3], "км")Вывод:
самая дальняя пара: ('Москва', 'Курск') — 540 км
расстояние Тула–Курск: 360 км
Граф и его представления
Граф состоит из вершин и рёбер. Его удобно хранить как список смежности — словарь, где для каждой вершины перечислены её соседи. Это компактнее матрицы, когда связей мало. Опишем небольшую сеть дружбы и посчитаем «популярность» (число связей) каждой вершины:
graph = {
"Аня": ["Боря", "Вера"],
"Боря": ["Аня", "Вера", "Гена"],
"Вера": ["Аня", "Боря"],
"Гена": ["Боря"],
}
print("Связи:")
for person, friends in graph.items():
print(f" {person}: {len(friends)} друзей — {friends}")
most = max(graph, key=lambda p: len(graph[p]))
print("Больше всего друзей у:", most)Вывод:
Связи: Аня: 2 друзей — ['Боря', 'Вера'] Боря: 3 друзей — ['Аня', 'Вера', 'Гена'] Вера: 2 друзей — ['Аня', 'Боря'] Гена: 1 друзей — ['Боря'] Больше всего друзей у: Боря
Обход графа в ширину
Фундаментальная операция — обойти все вершины, достижимые из данной. Обход в ширину (BFS) идёт «волнами»: сначала соседи, потом соседи соседей. Он же находит кратчайший путь по числу рёбер. Реализуем BFS с очередью и посчитаем, на каком «расстоянии» каждая вершина:
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
def bfs_levels(graph, start):
level = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in level: # ещё не посещали
level[neighbor] = level[node] + 1
queue.append(neighbor)
return level
result = bfs_levels(graph, "A")
for node in sorted(result):
print(f"до {node}: {result[node]} рёбер")Вывод:
до A: 0 рёбер до B: 1 рёбер до C: 1 рёбер до D: 2 рёбер до E: 2 рёбер до F: 2 рёбер
Взвешенный граф: кратчайший путь
Если рёбра имеют «вес» (длину, стоимость, время), задача усложняется: нужен путь минимального суммарного веса. Для маленьких графов его можно найти полным перебором всех путей. Найдём кратчайший маршрут из A в D в графе с весами:
edges = {
("A", "B"): 4, ("A", "C"): 2,
("C", "B"): 1, ("B", "D"): 5,
("C", "D"): 8, ("B", "C"): 1,
}
# построим список смежности с весами
adj = {}
for (u, v), w in edges.items():
adj.setdefault(u, []).append((v, w))
adj.setdefault(v, []).append((u, w))
best = [float("inf")]
def dfs(node, target, cost, visited):
if node == target:
best[0] = min(best[0], cost)
return
for nxt, w in adj.get(node, []):
if nxt not in visited:
dfs(nxt, target, cost + w, visited | {nxt})
dfs("A", "D", 0, {"A"})
print("кратчайший путь A→D:", best[0])Вывод:
кратчайший путь A→D: 8
Перебор путей нашёл маршрут A→C→B→D весом 2+1+5 = 8, что короче прямого A→C→D (2+8 = 10). Для больших графов используют специальные алгоритмы (например, Дейкстры), но идея «найти путь минимального веса» та же.
Попробуй сам
Проверим связность графа: достижимы ли из одной вершины все остальные. Это важнейшее свойство сетей — например, «дойдёт ли сигнал до каждого узла». Меняйте граф и смотрите.
graph = {
1: [2, 3],
2: [1, 4],
3: [1],
4: [2],
5: [], # изолированная вершина
}
def reachable(graph, start):
seen = set()
stack = [start]
while stack:
node = stack.pop()
if node not in seen:
seen.add(node)
stack.extend(graph[node])
return seen
from_one = reachable(graph, 1)
print("достижимо из 1:", sorted(from_one))
print("всего вершин:", len(graph))
print("граф связный:", len(from_one) == len(graph))Вывод:
достижимо из 1: [1, 2, 3, 4] всего вершин: 5 граф связный: False
Частые ошибки
- Не помечают посещённые вершины. Без множества «посещённых» обход графа с циклами зациклится навсегда.
- Путают матрицу смежности и список смежности. Матрица удобна для плотных графов, список — для разреженных.
- Забывают про симметрию неориентированного графа. Ребро A–B нужно занести в соседи и A, и B.
- Считают, что BFS даёт кратчайший путь по весу. BFS минимизирует число рёбер, а не их суммарный вес.
Итоги
- Табличная модель (матрица) описывает отношение между каждой парой объектов; в коде — список списков.
- Граф = вершины + рёбра; удобное представление — список смежности (словарь соседей).
- BFS обходит граф «волнами» и находит кратчайший путь по числу рёбер; обязательно помечать посещённые.
- Во взвешенном графе ищут путь минимального суммарного веса (перебором или алгоритмом Дейкстры).
