Алгоритмы на графах — Информатика, 11 класс

Кратчайшие пути во взвешенном графе, пути через заданный пункт, подсчёт количества путей, обходы в ширину и в глубину. 100 заданий на отработку.

Простыми словами

Граф — это схема «пункты и дороги между ними», как карта метро. Пункты называют вершинами, дороги — рёбрами. Если у дороги указана длина (время, цена), граф взвешенный; если по дороге можно ехать только в одну сторону (стрелка) — ориентированный, а дорога называется дугой.

Длина пути во взвешенном графе — сумма весов его рёбер. Кратчайший путь не обязан содержать наименьшее число рёбер: три короткие дороги могут оказаться короче одной длинной.

Кратчайший путь

Серые числа у вершин — кратчайшие расстояния от A. Выделен кратчайший путь A–B–C–D–E–G длины 11

Алгоритм (Дейкстры): начальной вершине ставим 0, остальным — «бесконечность». Берём вершину с наименьшей ещё не окончательной меткой $d [u]$ и улучшаем соседей:

если d [u] + w (u, v) < d [v], то d [v] := d [u] + w (u, v)

d

— найденное расстояние,

w (u, v)

— вес ребра

$A = 0$ . Соседи: $B = 3$ , $C = 5$ .
Из $B$ (3): $C = min (5, 3 + 1) = 4$ , $D = 9$ , $E = 12$ .
Из $C$ (4): $D = min (9, 4 + 2) = 6$ .
Из $D$ (6): $E = min (12, 6 + 3) = 9$ , $F = 10$ .
Из $E$ (9): $G = 11$ ; из $F$ : $10 + 5 = 15 > 11$ . Ответ: 11.

Через пункт Xкратчайший

A \to X

плюс кратчайший

X \to G

. Через

F

10 + 5 = 15

Дорога закрытасотрите её и пересчитайте. Без

E

–

G

остаётся путь через

F

15

Обход в ширину находит путь с наименьшим числом рёбер, а не с наименьшей суммой весов. Во взвешенном графе нужны метки расстояний.

Количество путей

В ориентированном графе без циклов число путей из $A$ в вершину $v$ равно сумме чисел путей во все вершины, из которых есть дуга в $v$ . Для $A$ число путей равно 1. Считаем в порядке, когда все дуги идут «слева направо».

B = A = 1

;

C = A + B = 2

;

D = B + C = 3

;

E = C + D = 5

;

F = D + E = 8

путей

Через вершину C(путей

A \to C

) · (путей

C \to F

)

= 2 \cdot 3 = 6

Не через Cвсе пути минус пути через C:

8 - 6 = 2

(A–B–D–F и A–B–D–E–F)

Чтобы обойти вершину X, проще всего «стереть» её вместе с дугами и пересчитать суммы заново.

Обходы и пути длины 2

В глубину (DFS)идём как можно дальше к первому непосещённому соседу; тупик — возвращаемся на шаг назад. Работает как стек.

В ширину (BFS)сначала все соседи стартовой вершины, потом их соседи по очереди. Работает как очередь.

Соседи: A — B, C; B — A, D; C — A, D, E; D — B, C; E — C. Перебор по алфавиту, старт A.

DFS: A → B → D → C (сосед D) → E. Порядок: A, B, D, C, E.
BFS: A; соседи A: B, C; соседи B: D; соседи C: E. Порядок: A, B, C, D, E.

Путей ровно из двух дорог из $u$ в $v$ столько, сколько вершин $w$ , для которых в таблице есть «+» в строке $u$ столбце $w$ и в строке $w$ столбце $v$ . Перебираем все промежуточные $w$ .

Таблица весов и свойства путей

В таблице весов на пересечении строки $u$ и столбца $v$ стоит длина дороги $u$ – $v$ ; прочерк (пустая клетка) означает, что прямой дороги нет. Таблица неориентированного графа симметрична относительно главной диагонали.
Если кратчайший путь из A в B проходит через C, то его часть от A до C — тоже кратчайший путь из A в C (иначе весь путь можно было бы укоротить).
Если в ориентированном графе есть цикл, число путей между некоторыми вершинами может быть бесконечным: по циклу можно пройти сколько угодно раз. Поэтому метод сумм применяют к графам без циклов.

Примеры заданий

Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.

В таблице знаком «+» отмечены пары пунктов, соединённые дорогой с односторонним движением (строка — откуда, столбец — куда). Сколько существует путей из A в C, состоящих ровно из двух дорог?

	B	C	D	F
A	+		+
B		+	+
C			+
D				+
E				+
F

Показать ответ

Ответ: 1
Решение. Подходят промежуточные пункты: B — всего 1 путь.

В таблице знаком «+» отмечены пары пунктов, соединённые дорогой с односторонним движением (строка — откуда, столбец — куда). Сколько существует путей из A в D, состоящих ровно из двух дорог?

	B	C	D	E	F
A	+
B		+	+	+
C			+		+
D
E
F

Показать ответ

Ответ: 1
Решение. Подходят промежуточные пункты: B — всего 1 путь.

В таблице знаком «+» отмечены пары пунктов, соединённые дорогой с односторонним движением (строка — откуда, столбец — куда). Сколько существует путей из B в F, состоящих ровно из двух дорог?

	C	D	E	F
A	+	+		+
B	+		+	+
C		+		+
D
E
F

Показать ответ

Ответ: 1
Решение. Подходят промежуточные пункты: C — всего 1 путь.

В таблице знаком «+» отмечены пары пунктов, соединённые дорогой с односторонним движением (строка — откуда, столбец — куда). Сколько существует путей из C в E, состоящих ровно из двух дорог?

	B	D	E	F
A	+	+
B			+
C		+	+	+
D			+
E
F

Показать ответ

Ответ: 1
Решение. Подходят промежуточные пункты: D — всего 1 путь.

В таблице знаком «+» отмечены пары пунктов, соединённые дорогой с односторонним движением (строка — откуда, столбец — куда). Сколько существует путей из A в E, состоящих ровно из двух дорог?

	C	D	E	F
A	+	+
B	+		+
C		+
D			+	+
E
F

Показать ответ

Ответ: 1
Решение. Подходят промежуточные пункты: D — всего 1 путь.

Длина пути во взвешенном графе — это

Задача	Как решается
кратчайший путь	наименьшая сумма весов рёбер
число путей в вершину	сумма чисел путей во все вершины, откуда ведёт дуга
пути через вершину C	(пути A → C) · (пути C → конец)
обход в ширину	по слоям, находит путь с наименьшим числом рёбер
обход в глубину	как можно дальше по ветви, затем возврат

наибольший вес ребра пути
количество рёбер пути
количество вершин пути
сумма весов входящих в него рёбер

Показать ответ

Ответ: сумма весов входящих в него рёбер
Решение. Вес ребра — длина, стоимость или время, и они складываются вдоль пути.