Графы — модели и задачи
Зачем программисту графы
Граф — множество вершин (узлов) и рёбер (связей между ними). Одна и та же абстракция описывает дороги на карте, дружбу в соцсети, гиперссылки между страницами, зависимости в сборке проекта или цепочки вызовов в программе.
Классический пример — мосты Кёнигсберга (XVIII век) — можно ли пройти по каждому мосту ровно один раз? Леонард Эйлер свёл задачу к графу и показал, что ответ зависит только от чётности степеней вершин, а не от длины мостов. С тех пор графы — стандартный язык для задач "кто с кем связан и как пройти от A до B".
Основные определения
| Термин | Смысл |
|---|---|
| Вершина (узел) | Объект: город, страница, пользователь, функция |
| Ребро (дуга, звено) | Связь между двумя вершинами |
| Направленный граф | Ребро имеет направление (A → B, но не обязательно B → A) |
| Ненаправленный граф | Связь симметрична |
| Вес ребра | Число на связи: расстояние, время, стоимость, "важность" ссылки |
| Путь | Цепочка рёбер, соединяющая вершины |
| Цикл | Путь, начинающийся и заканчивающийся в одной вершине |
| Ациклический граф | Без циклов (важно для DAG в планировании и сборках) |
Степень вершины — число рёбер, с которыми она соединена. В задаче Кёнигсберга эйлеров цикл существует, только если у всех вершин чётная степень (с уточнениями для несвязных компонент).
Как хранить граф в программе
Play ITЗагрузка интерактивного демо…
Play ITЗагрузка интерактивного демо…
Play ITЗагрузка интерактивного демо…
| Представление | Когда удобно |
|---|---|
| Список смежности | Разреженные графы, обход соседей |
| Матрица смежности | Плотные графы, быстрая проверка "есть ли ребро" |
| Матрица весов | Кратчайшие пути, небольшие n |
В списке смежности для каждой вершины хранят список соседей (и весов). Память порядка O(V + E) для V вершин и E рёбер.
Типичные задачи
| Задача | Идея | Куда глубже |
|---|---|---|
| Обход всех вершин | BFS — в ширину (очередь), DFS — в глубину (стек/рекурсия) | структуры данных |
| Кратчайший путь | Жадная релаксация расстояний | Дейкстра |
| Связность | Достижимость из точки | обход BFS/DFS |
| Ранжирование важности | Распространение "голосов" по ссылкам | PageRank |
| Коммивояжёр | Обойти все вершины с минимальной суммой весов | алгоритмическое мышление — перебор O(n!) |
Обход в ширину (BFS) находит кратчайший путь в неневзвешенном графе (каждое ребро "стоит" 1). Обход в глубину (DFS) удобен для проверки циклов, топологической сортировки зависимостей.
Формальные критерии (Эйлер, Гамильтон, остовы, раскраски) — в теории графов; ниже — то, что чаще всего пишут в коде.
Эйлеров и гамильтонов циклы
| Цикл | Проходит | Критерий (идея) | Практика |
|---|---|---|---|
| Эйлеров | каждое ребро ровно раз | в связном неорграфе все степени чётны | обход всех рёбер сети, маршрут инспекции |
| Гамильтонов | каждую вершину ровно раз | в общем случае NP-трудно; есть достаточные условия на степени | коммивояжёр, доставка, сверление плат |
Задача коммивояжёра — гамильтонов цикл минимального веса. Полный перебор O(n!); на практике — эвристики и приближения.
DAG и топологическая сортировка
Ориентированный ациклический граф (DAG) — нет направленных циклов. Моделирует зависимости: модуль B импортирует A, задача C ждёт B.
Топологическая сортировка — порядок вершин, в котором все рёбра идут "слева направо". Существует только для DAG. Реализация — DFS с выводом вершин в обратном порядке завершения или алгоритм Кана (очередь вершин с нулевым входящим счётчиком).
// Проверка: можно ли собрать проект (упрощённо)
если в графе зависимостей есть цикл то
Ошибка("циклическая зависимость")
иначе
порядок := топологическая_сортировка(граф)
для каждого модуля m в порядок
Собрать(m)
конец
конец
Минимальный остов (MST)
Остов связного графа — подмножество рёбер, связывающее все вершины без циклов (n−1 ребро для n вершин). Минимальный остов — остов с минимальной суммой весов.
| Алгоритм | Идея | Сложность (типично) |
|---|---|---|
| Прим | растим дерево из старта, каждый раз добавляем ребро минимального веса к новой вершине | O(E log V) с кучей |
| Краскал | сортируем рёбра по весу, добавляем, если не образует цикл (система непересекающихся множеств) | O(E log E) |
Применение — проектирование сети связи, кластеризация, когда нужен "дешёвый каркас" без лишних циклов.
АЛГОРИТМ BFS(G, старт)
создать очередь Q
пометить старт как посещённую
добавить старт в Q
пока Q не пуста
v := извлечь из начала Q
для каждого соседа u вершины v
если u ещё не посещена
пометить u
добавить u в Q
конец если
конец для
конец пока
КОНЕЦ
Графы вокруг нас
- Социальные сети — вершины люди, рёбра "дружба" или "подписка".
- Веб — страницы и гиперссылки (PageRank).
- Маршруты — перекрёстки и дороги с длиной (Дейкстра).
- Сборка ПО — модули и зависимости (DAG, без циклов).
- Параллельные вычисления — граф зависимостей операторов (граф алгоритма).
Для взвешенных дорог с неотрицательными весами — алгоритм Дейкстры. Для оценки "важности" страниц в сети ссылок — PageRank.
Связанные материалы
- Сортировка и поиск — линейные структуры до графов
- Нотация Большое O — сложность обходов
O(V + E) - Big-O — шпаргалка с примерами — почему BFS/DFS линейны по
V+E, ловушкиdequeвместоpop(0) - Дискретная математика, графы — углубление
- Алгоритмы — о разделе — маршрут раздела
- Алгоритмы на Python — ЕГЭ и олимпиадка — BFS/DFS на сетке и списке смежности с разбором строк
- Pascal / Free Pascal — типовые программы — массив, поиск, сортировка (консольные задачи до графов)