10 мин чтенияграфыдеревообходкратчайший путьКЕГЭ
Графы и основы алгоритмов на графах
Представление графов, поиск пути, подсчёт числа путей, кратчайшие пути, деревья и обход в глубину и ширину.
Открываем тему…
Основные понятия
Граф — множество вершин и рёбер. Ребро может быть ориентированным (дуга) и иметь вес. Путь — последовательность вершин, соединённых рёбрами; цикл — путь, возвращающийся в начальную вершину. Дерево — связный граф без циклов, у которого n вершин и n − 1 ребро.
Интерактивная иллюстрация
- Матрица смежности — таблица n×n; список смежности — для каждой вершины список соседей (экономит память).
- Степень вершины — число инцидентных рёбер; сумма степеней равна удвоенному числу рёбер.
- Эйлеров путь существует, если число вершин нечётной степени равно 0 или 2.
Число путей и кратчайшие пути
Для ориентированного ациклического графа число путей из A в вершину X равно сумме чисел путей из A во все вершины, из которых в X ведёт дуга. Вычисляют вершины в топологическом порядке (или рекурсивно с кэшированием).
ПримерЧисло путей
Дуги графа: A→B, A→C, B→D, C→D, B→C, D→E, C→E. Сколько путей из A в E?
Решение
paths(A)=1; B=1 (A→B); C=paths(A)+paths(B)=2; D=paths(B)+paths(C)=3; E=paths(D)+paths(C)=5.
ПримерКратчайший путь (алгоритм Дейкстры)
Найдите минимальную длину пути от вершины 0 до вершины 4 во взвешенном графе, заданном словарём.
Решение
import heapq
def dijkstra(g, s):
dist = {s: 0}
pq = [(0, s)]
while pq:
d, v = heapq.heappop(pq)
if d > dist.get(v, 1e18):
continue
for u, w in g[v]:
nd = d + w
if nd < dist.get(u, 1e18):
dist[u] = nd
heapq.heappush(pq, (nd, u))
return dist
g = {0: [(1, 4), (2, 1)], 1: [(4, 1)], 2: [(1, 2), (4, 7)], 4: []}
print(dijkstra(g, 0)[4]) # 4
ПримерЧисло путей через обязательную вершину
Дуги графа: A→B, A→C, B→D, C→D, B→E, C→E, D→E, D→F, E→F. Сколько путей из A в F проходит через вершину D?
Решение
Путь через D разбивается на участки A→D и D→F; число путей умножается. Из A в D: A→B→D и A→C→D — 2 пути. Из D в F: D→F и D→E→F — 2 пути. Итого 2·2 = 4.
Общее число путей из A в F: paths(E) = paths(B) + paths(C) + paths(D) = 1 + 1 + 2 = 4, paths(F) = paths(D) + paths(E) = 2 + 4 = 6; 4 из них проходят через D.
Обходы
- Поиск в ширину (BFS) использует очередь и находит кратчайший путь в невзвешенном графе.
- Поиск в глубину (DFS) использует стек или рекурсию, подходит для проверки связности и поиска циклов.
- Для таблицы расстояний между пунктами по заданной матрице сопоставьте вершины с рёбрами через степени вершин.
ПримерПоиск в ширину: минимум рёбер
Граф задан словарём смежности {1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: []}. Найдите наименьшее число рёбер в пути из 1 в 6.
Решение
from collections import deque
g = {1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: []}
dist = {1: 0}
q = deque([1])
while q:
v = q.popleft()
for u in g[v]:
if u not in dist:
dist[u] = dist[v] + 1
q.append(u)
print(dist[6]) # 3
Вручную: 1 → 2 → 4 → 6 (3 ребра); пути короче нет.
ПримерЭйлеров путь
Связный граф имеет вершины степеней 3, 3, 2, 2, 4. Можно ли пройти по каждому ребру ровно один раз? Сколько в графе рёбер?
Решение
Эйлеров путь в связном графе существует, если вершин нечётной степени 0 или 2. Здесь нечётных вершин две (обе степени 3) — путь существует, он должен начинаться в одной из них и заканчиваться в другой. Сумма степеней 3 + 3 + 2 + 2 + 4 = 14 равна удвоенному числу рёбер, поэтому рёбер 7.