графы

1.

ОЛИМПИАДНОЕ ПРОГРАММИРОВАНИЕ
Графы: от ребер к кратчайшему пути
1
DFS • BFS • Дейкстра • кратчайший путь
2
5
3
4
СЕГОДНЯ НАУЧИМСЯ
строить граф • обходить вершины • находить кратчайший путь
1

2.

ГРАФЫ • PYTHON
Маршрут занятия
01
Граф и связи
Вершины, ребра, типы
02
Хранение
Список смежности
03
DFS
Обход и компоненты
04
BFS
Очередь и расстояния
05
Веса и задачи
Дейкстра • олимпиадный разбор
Сначала разбираем алгоритмы, затем решаем задачи самостоятельно.
2

3.

ГРАФЫ • PYTHON
Дерево — частный случай графа
ДЕРЕВО
ОБЫЧНЫЙ ГРАФ
1
2
4
1
3
5
Связно • нет циклов • m = n − 1
2
3
4
5
Возможны циклы и разные маршруты
Граф = множество вершин V и множество ребер E. В дереве между двумя вершинами только один простой путь.
3

4.

ГРАФЫ • PYTHON
Какие признаки графа важны в условии?
Неориентированный
Ориентированный
Ребро 1—2 разрешает движение в обе стороны.
Дуга 1→2 не означает, что можно идти 2→1.
Невзвешенный
Взвешенный
Каждый переход стоит один шаг. Для
кратчайшего пути подходит BFS.
У ребер есть стоимости. При неотрицательных
весах обычно применяют Дейкстру.
Перед выбором алгоритма выясните: есть ли направление, веса и что нужно найти.
4

5.

ГРАФЫ • PYTHON
Список смежности — основной формат
СПИСОК СОСЕДЕЙ
2
g[1] = [2, 3]
g[2] = [1, 4]
g[3] = [1, 4]
g[4] = [2, 3, 5]
g[5] = [4]
1
3
4
5
Память: O(n + m)
В неориентированном графе каждое ребро записываем дважды: a → b и b → a.
5

6.

ГРАФЫ • PYTHON
Олимпиадный ввод: строим граф
ВХОДНЫЕ ДАННЫЕ
55
12
13
24
34
45
Ориентация
КОД НА PYTHON
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
Если ребра направленные, уберите строку g[b].append(a).
6

7.

ГРАФЫ • PYTHON
Зачем нужен массив visited?
DFS: ПОМЕЧАЕМ ПРИ ВХОДЕ
seen = [False] * (n + 1)
1
2
3
def dfs(v):
seen[v] = True
for u in g[v]:
if not seen[u]:
dfs(u)
dfs(1)
1→2→3→1→…
Циклы не мешают DFS, если каждая вершина посещается не более одного раза.
7

8.

ГРАФЫ • PYTHON
DFS: сначала вглубь, затем возврат
ПРИ СОРТИРОВКЕ СОСЕДЕЙ
2
4
1→2→4→5→6→3
1
5
3
6
DFS идет к первому
непосещенному соседу и
возвращается, когда дальше идти
некуда.
Порядок обхода зависит от порядка соседей. Достижимость — не зависит.
8

9.

ГРАФЫ • PYTHON
Компоненты связности считаем через DFS
1
seen = [False] * (n + 1)
components = 0
4
2
3
ЗАПУСКАЕМ DFS ОТ КАЖДОЙ НОВОЙ
4, 5
КОМПОНЕНТ: 1, 2, 3
5
for start in range(1, n + 1):
if not seen[start]:
components += 1
dfs(start)
print(components) # 3
6
6
Одна DFS охватывает одну компоненту. Изолированная вершина — тоже компонента.
9

10.

ГРАФЫ • PYTHON
Если граф большой: DFS через стек
ИТЕРАТИВНЫЙ DFS
stack = [start]
seen[start] = True
while stack:
v = stack.pop()
for u in g[v]:
if not seen[u]:
seen[u] = True
stack.append(u)
ПОЧЕМУ ЭТО ВАЖНО
Цепочка из 200 000 вершин
Рекурсивный DFS может упереться в лимит
глубины вызовов Python.
Явный стек
Обходит граф за O(n + m) без углубления
стека вызовов Python.
Помечайте соседа до помещения в стек, чтобы не добавлять его повторно.
10

11.

ГРАФЫ • PYTHON
BFS: очередь и расстояния по слоям
СЛОИ ОТ ВЕРШИНЫ 1
2
1
4
0:
1:
2:
3:
5
1
2, 3
4, 5, 6
7
7
3
6
Очередь FIFO: первый вошел —
первый вышел.
В невзвешенном графе BFS находит минимальное число ребер от источника.
11

12.

ГРАФЫ • PYTHON
BFS на Python: расстояния
ПОИСК В ШИРИНУ
from collections import deque
dist = [-1] * (n + 1)
dist[s] = 0
q = deque([s])
while q:
v = q.popleft()
for u in g[v]:
if dist[u] == -1:
dist[u] = dist[v] + 1
q.append(u)
dist[u] == -1
Вершина еще не посещена. Число
−1 также означает недостижимость.
dist[v] + 1
Любое новое ребро добавляет ровно
один шаг.
Используйте deque.popleft(): удаление первого элемента — O(1), в отличие от list.pop(0).
12

13.

ГРАФЫ • PYTHON
Как выбрать алгоритм под задачу?
ЧТО ТРЕБУЕТСЯ
АЛГОРИТМ
ПОЧЕМУ
Проверить достижимость
DFS / BFS
Достаточно посетить вершины
Посчитать компоненты
DFS / BFS
Новый запуск = новая компонента
Кратчайший путь без весов
BFS
Первое обнаружение дает минимум
ребер
Кратчайший путь с весами ≥ 0
Дейкстра
Число ребер не равно стоимости пути
Сравним BFS и Дейкстру на одном графе — затем разберем код.
13

14.

ГРАФЫ • PYTHON
Веса ребер: меньше шагов — не всегда дешевле
ОДИН ГРАФ — ДВА КРИТЕРИЯ
BFS • МЕНЬШЕ РЕБЕР
10
3
2
1
2
1
9
4
2
1→2→4
2 ребра • вес 9 + 2 = 11
ДЕЙКСТРА • МЕНЬШЕ СТОИМОСТЬ
1→3→2→4
Все ребра неориентированные
3 ребра • вес 2 + 1 + 2 = 5
BFS минимизирует число ребер. Дейкстра находит минимальную сумму неотрицательных весов.
14

15.

ГРАФЫ • PYTHON
Взвешенный граф: храним пары (сосед, вес)
ВХОДНЫЕ ДАННЫЕ
4514
129
132
231
242
3 4 10
КОД НА PYTHON
n, m, s, t = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, w = map(int, input().split())
g[a].append((b, w))
g[b].append((a, w))
Например: g[1] = [(2, 9), (3, 2)]
Для неориентированного графа добавляем обе стороны; для ориентированного — только g[a].
15

16.

ГРАФЫ • PYTHON
Алгоритм Дейкстры: heapq + улучшение расстояния
НАХОДИМ МИНИМАЛЬНУЮ СУММУ ВЕСОВ
import heapq
ПОЧЕМУ HEAPQ?
dist = [float('inf')] * (n + 1)
dist[s] = 0
pq = [(0, s)]
while pq:
d, v = heapq.heappop(pq)
if d != dist[v]:
continue
for u, w in g[v]:
nd = d + w
if nd < dist[u]:
dist[u] = nd
heapq.heappush(pq, (nd, u))
Сначала извлекаем вершину с
наименьшей текущей
стоимостью.
НА ПРИМЕРЕ
dist[2]: 9 → 3
dist[4]: 12 → 5
Ответ: 5
Работает для весов ≥ 0. Если dist[t] остался inf, путь не существует.
16

17.

ГРАФЫ • PYTHON
Олимпиадная задача • кратчайший путь
Невзвешенный неориентированный граф: найти маршрут s → t с минимальным числом ребер.
ВВОД
2
4
7
5
1
3
7817
12
13
24
45
35
36
56
67
6
ВЫВОД
3
1367
Выделенный путь
содержит три
ребра.
Формат: n m s t; далее m строк a b. Ограничения: n, m ≤ 200 000. Любой кратчайший путь подходит.
Вывод: −1, если пути нет; иначе число ребер и вершины маршрута.
17

18.

ГРАФЫ • PYTHON
BFS: слои, parent и восстановление
РАССТОЯНИЯ ОТ ВЕРШИНЫ 1
0 ребер
1
1 ребро
2, 3
2 ребра
4, 5, 6
3 ребра
7
ПРИ ПЕРВОМ ОБНАРУЖЕНИИ
parent[u] = v
q.append(u)
ВОССТАНАВЛИВАЕМ МАРШРУТ
7→6→3→1
Развернули: 1 → 3 → 6 → 7
Длина: 3 ребра
Очередь FIFO: сначала обрабатываем близкие вершины.
BFS обходит вершины по слоям: первое обнаружение дает кратчайший путь. Время O(n + m).
18

19.

ГРАФЫ • PYTHON
Полное решение • BFS и восстановление пути
from collections import deque
import sys
input = sys.stdin.buffer.readline
n, m, s, t = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
parent = [-1] * (n + 1)
parent[s] = s
q = deque([s])
while q:
v = q.popleft()
for u in g[v]:
if parent[u] == -1:
parent[u] = v
q.append(u)
if parent[t] == -1:
print(-1)
else:
path = [t]
while path[-1] != s:
path.append(parent[path[-1]])
print(len(path) - 1)
print(*path[::-1])
19

20.

ПРАКТИКА • САМОСТОЯТЕЛЬНО
Задача 1 • Степени вершин
Уровень: базовый. Начните со списка смежности или массива степеней.
УСЛОВИЕ
Дан неориентированный граф. Выведите
степень каждой вершины: сколько ребер с
ней связано.
ПРИМЕР ВВОДА
54
12
13
34
35
ВЫВОД
21311
1 ≤ n ≤ 200 000
0 ≤ m ≤ 200 000
Петли отсутствуют.
Дополнительно: оцените время и память своего решения.
20

21.

ПРАКТИКА • САМОСТОЯТЕЛЬНО
Задача 2 • Число компонент связности
Уровень: базовый+. Подойдет DFS со стеком или BFS.
УСЛОВИЕ
Дан неориентированный граф. Выведите
число его компонент связности.
ПРИМЕР ВВОДА
73
12
23
56
ВЫВОД
4
Изолированные вершины тоже считаются.
Ограничения: n, m ≤ 200 000.
Самопроверка: компоненты {1,2,3}, {4}, {5,6}, {7}.
21

22.

ПРАКТИКА • САМОСТОЯТЕЛЬНО
Задача 3 • Минимальное число ребер
Уровень: основной. Нужна только длина кратчайшего пути, без маршрута.
УСЛОВИЕ
В неориентированном невзвешенном
графе найдите минимальное число ребер
на пути из s в t.
Если пути нет, выведите −1.
Подсказка: dist и BFS.
ПРИМЕР ВВОДА
6616
12
13
24
35
45
56
ВЫВОД
3
Проверьте отдельно s = t и ситуацию, когда t недостижима.
22

23.

ПРАКТИКА • САМОСТОЯТЕЛЬНО
Задача 4 • Путь в ориентированном графе
Уровень: основной+. Выводите любой кратчайший маршрут.
УСЛОВИЕ
Повторите олимпиадную задачу, но ребра
теперь направленные. Выведите −1 или
длину и вершины кратчайшего пути.
Что поменять: при чтении добавляйте только дугу
a → b.
ПРИМЕР ВВОДА
6716
12
13
24
34
35
46
56
ОДИН ИЗ ОТВЕТОВ
3
1246
Если найден другой путь длины 3, он тоже правильный.
23

24.

ПРАКТИКА • САМОСТОЯТЕЛЬНО
Задача 5 • Минимальная стоимость пути
Уровень: основной+. Используйте алгоритм Дейкстры, не BFS.
УСЛОВИЕ
Дан неориентированный взвешенный граф.
Найдите минимальную сумму весов на пути из
s в t.
Если пути нет — выведите −1.
1 ≤ n ≤ 200 000; 0 ≤ m ≤ 200 000
0 ≤ w ≤ 10⁹.
ПРИМЕР ВВОДА
4514
129
132
231
242
3 4 10
ВЫВОД
5
Подсказка: heapq, dist и обновление dist[u], если нашлась меньшая сумма весов.
24

25.

ДОПОЛНИТЕЛЬНЫЕ ЗАДАЧИ • ПРОДВИНУТЫЙ УРОВЕНЬ
Продвинутым • BFS с несколькими источниками
ЗАДАЧА
Дан граф и набор стартовых вершин S. Для каждой
вершины найдите расстояние до ближайшей
вершины из S.
ПРИМЕР
Граф-цепочка: 1—2—3—4—5—6
S = {1, 6}
Подсказка: добавьте все вершины из S в очередь сразу,
установив им расстояние 0.
Расстояния:
012210
Усложнение: обрабатывайте n, m ≤ 200 000 за O(n + m).
25

26.

ДОПОЛНИТЕЛЬНЫЕ ЗАДАЧИ • ПРОДВИНУТЫЙ УРОВЕНЬ
Продвинутым • Проверка двудольности
ЗАДАЧА
ТРЕУГОЛЬНИК: НЕТ
Можно ли покрасить вершины графа в два
цвета так, чтобы концы каждого ребра имели
разные цвета?
Подсказка: BFS + color[v] ∈ {0, 1}. Не забудьте про
разные компоненты.
1
2
3
Нечетный цикл нельзя покрасить двумя
цветами.
Оцените сложность: O(n + m). Проверьте также граф без ребер и две отдельные компоненты.
26