Графы и поиск кратчайшего пути
💻 Информатика · 11 класс
Что такое граф
Граф — это математическая модель, состоящая из вершин и соединяющих их рёбер. Графами описывают дороги между городами, связи в социальных сетях, схемы метро, расписания и многое другое. В одиннадцатом классе графы изучают как способ моделирования и как основу для алгоритмов поиска пути, которые встречаются и в экзаменационных задачах.
Если ребро имеет направление, граф называют ориентированным. Если каждому ребру приписан вес (расстояние, стоимость, время), граф называют взвешенным. Степень вершины — это число выходящих из неё рёбер.
Способы хранения графа
Граф в программе хранят двумя основными способами, и каждый удобен для своих задач.
- Матрица смежности — квадратная таблица, где на пересечении строки и столбца стоит вес ребра или ноль, если связи нет. Удобна, когда рёбер много.
- Список смежности — для каждой вершины перечислены её соседи. Экономит память, когда рёбер немного.
Ниже взвешенный граф задан перечислением рёбер с их весами.
| Из вершины | В вершину | Вес ребра |
|---|---|---|
| А | Б | 5 |
| А | В | 2 |
| В | Б | 1 |
| Б | Г | 4 |
Обходы графа
Обход в ширину начинает с вершины и посещает сначала всех её соседей, затем соседей соседей, расходясь волнами. Он использует очередь и находит путь с наименьшим числом рёбер. Обход в глубину идёт вглубь по одному пути до упора, затем возвращается назад и пробует другие ветви; он опирается на стек или рекурсию. Оба обхода помечают посещённые вершины, чтобы не зациклиться.
Поиск кратчайшего пути
Для взвешенного графа без отрицательных весов кратчайшие расстояния находит алгоритм Дейкстры. Идея проста: на каждом шаге выбираем ещё не обработанную вершину с наименьшим известным расстоянием и пробуем улучшить расстояния до её соседей.
Старт А, расстояния: А=0, остальные = бесконечность
Из А: Б=5, В=2
Берём В (минимум): через В путь до Б = 2+1 = 3 < 5, обновляем Б=3
Берём Б: до Г = 3+4 = 7
Итог: кратчайший путь А -> В -> Б -> Г длиной 7Без алгоритма легко ошибиться: прямой путь А -> Б -> Г равен 5+4=9, а обход через вершину В оказывается короче и равен 7. Алгоритм перебирает варианты системно и гарантированно находит самый дешёвый маршрут.
Связные графы и деревья
Граф называют связным, если из любой вершины можно добраться до любой другой по рёбрам. Особый вид связного графа без циклов — дерево: в нём между двумя вершинами существует ровно один путь. Деревья описывают иерархии: файловую систему, генеалогию, структуру организации. У дерева из n вершин всегда ровно n-1 рёбер, и добавление ещё одного ребра обязательно образует цикл.
Частые ошибки. Применяют алгоритм Дейкстры при отрицательных весах — там он даёт неверный ответ. Путают обход в ширину и поиск кратчайшего пути по весам: обход в ширину минимизирует число рёбер, а не их суммарный вес. Забывают помечать посещённые вершины и зацикливаются.
Кратко о главном
- Граф — это вершины и рёбра; бывает ориентированным и взвешенным.
- Хранят графы матрицей или списком смежности.
- Обход в ширину использует очередь, в глубину — стек или рекурсию.
- Алгоритм Дейкстры находит кратчайшие пути при неотрицательных весах.
- Посещённые вершины помечают, чтобы не зациклиться.