3.14 Алгоритмы на графах. Построение минимального остовного дерева взвешенного связного неориентированного графа. Количество различных путей между вершинами ориентированного ациклического графа. Алгоритм Дейкстры — Подготовка к ЕГЭ/ОГЭ и сессии СПО и ВУЗы

Алгоритмы на графах для ЕГЭ по информатике

Разберем ключевые алгоритмы работы с графами, которые встречаются в заданиях ЕГЭ.

1. Минимальное остовное дерево

Остовное дерево — подграф, который является деревом и содержит все вершины исходного графа.

Минимальное остовное дерево (МОД) — остовное дерево с минимальной суммой весов его рёбер.

Алгоритм Крускала

1. Создаём множество рёбер будущего дерева

2. Сортируем все рёбра по весу (по возрастанию)

3. Добавляем рёбра с минимальным весом, которые не образуют цикл

4. Повторяем, пока не добавлены все вершины

Алгоритм Прима

1. Выбираем произвольную вершину для начала

2. Находим ребро с минимальным весом к новой вершине

3. Добавляем это ребро и вершину в дерево

4. Повторяем, пока все вершины не включены

Сравнение алгоритмов

Критерий	Алгоритм Крускала	Алгоритм Прима
Сложность	O(E log V)	O(V²) или O(E + V log V)
Используемые структуры	Система непересекающихся множеств	Очередь с приоритетом
Подход	Жадный, на основе рёбер	Жадный, на основе вершин

2. Количество путей в ориентированном ациклическом графе (DAG)

Ориентированный ациклический граф (DAG) — граф без циклов с ориентированными рёбрами.

Алгоритм подсчёта путей

1. Выполняем топологическую сортировку вершин

2. Создаём массив dp, где dp[i] — количество путей до i-й вершины

3. Инициализируем dp[начальной вершины] = 1

4. Для каждой вершины в порядке топологической сортировки обновляем значения

Пример топологической сортировки

→

Топологический порядок: A, B, C, D, E, F

3. Алгоритм Дейкстры

Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных в графе с неотрицательными весами.

Шаги алгоритма

1. Инициализируем расстояния до всех вершин как бесконечность, кроме начальной (0)

2. Создаём множество непосещённых вершин

3. Пока есть непосещённые вершины:

— Выбираем вершину с минимальным расстоянием

— Обновляем расстояния до всех соседей

— Помечаем текущую вершину как посещённую

Сложность алгоритма Дейкстры

Структура данных	Сложность
Массив	O(V²)
Двоичная куча	O((V+E) log V)
Фибоначчиева куча	O(E + V log V)

Примеры задач

Пример 1: Минимальное остовное дерево

Найдите минимальное остовное дерево для графа с вершинами A, B, C, D и рёбрами:

A-B: вес 3
A-C: вес 1
B-C: вес 2
B-D: вес 4
C-D: вес 5

Решение: Рёбра МОД: A-C(1), B-C(2), B-D(4). Сумма весов: 7.

Пример 2: Количество путей в DAG

Сколько различных путей от вершины A до вершины D в графе:

A → B, A → C, B → D, C → D

Решение: 2 пути (A→B→D и A→C→D).

Пример 3: Алгоритм Дейкстры

Найдите кратчайшие пути от вершины A до всех остальных:

   A --2-- B
   |       |
   4       3
   |       |
   C --1-- D

Решение:

A→A: 0
A→B: 2
A→C: 4
A→D: 5 (A→B→D)

Заключение

Эти алгоритмы являются фундаментальными для работы с графами и часто встречаются в задачах ЕГЭ по информатике. Понимание их работы и умение применять на практике — ключ к успешному решению задач.

Для закрепления материала рекомендуется решать практические задачи и реализовывать алгоритмы на языке программирования.