Граф — вершины и связи между ними. Чтобы решать на нём задачи, граф нужно хранить в программе и знать несколько классических алгоритмов.
Что нужно знать
- Степень вершины — число инцидентных ей рёбер; сумма степеней = 2 · число рёбер.
- Матрица смежности n × n (у неориентированного графа симметрична); списки смежности — словарь {вершина: [соседи]}; список рёбер — пары (и веса).
- Жадный алгоритм берёт локально лучший шаг; оптимален не всегда (монеты 1, 3, 4 для суммы 6).
- Остовное дерево связывает все n вершин n − 1 рёбрами. Краскал: рёбра по возрастанию веса, пропускать те, что замыкают цикл.
- Дейкстра: метка старта 0, остальных ∞; брать необработанную вершину с наименьшей меткой, улучшать метки соседей. Веса — только неотрицательные.
- Флойд — Уоршелл: для k, i, j: d[i][j] = min(d[i][j], d[i][k] + d[k][j]); все пары, n³; d[i][i] < 0 — отрицательный цикл.
- Невзвешенный кратчайший путь — обход в ширину (очередь).
- Списки смежности экономнее для разреженных графов, матрица — удобна для плотных и для Флойда.
Где чаще всего ошибаются
- Применять Дейкстру к графу с отрицательными рёбрами.
- Считать одно ребро неориентированного графа одной единицей в матрице смежности.
- Брать в остовное дерево ребро, которое замыкает цикл.
- Верить, что жадный выбор всегда даёт оптимальный ответ.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Алгоритмы и структуры данных · 9 класс · Графы и алгоритмы на графах