Список смежности
Список смежности — это один из основных способов представления графа в памяти компьютера, при котором для каждой вершины графа хранится список (или иная коллекция) смежных с ней вершин. Данный метод широко применяется в алгоритмах на графах, таких как поиск в ширину (BFS), поиск в глубину (DFS), алгоритмы нахождения кратчайших путей (алгоритм Дейкстры, алгоритм Беллмана — Форда) и алгоритмы нахождения минимального остовного дерева (алгоритм Прима, алгоритм Краскала). Список смежности является альтернативой матрице смежности и матрице инцидентности.
Определение и основные понятия
Пусть задан граф \( G = (V, E) \), где \( V \) — множество вершин, а \( E \) — множество рёбер. Список смежности для каждой вершины \( v \in V \) содержит все вершины \( u \in V \), такие что существует ребро \( (v, u) \in E \). Для неориентированных графов каждое ребро \( \{v, u\} \) учитывается дважды: в списке вершины \( v \) и в списке вершины \( u \). Для ориентированных графов ребро \( (v, u) \) добавляется только в список вершины \( v \).
Взвешенные графы
В случае взвешенных графов в списке смежности хранятся не только идентификаторы смежных вершин, но и веса соответствующих рёбер. Обычно для этого используется структура данных, содержащая пару (вершина, вес) или кортеж.
Реализация
Список смежности может быть реализован различными способами в зависимости от языка программирования и требований к производительности.
Массив списков
Наиболее распространённая реализация — массив (или вектор) фиксированного размера \( |V| \), каждый элемент которого является списком (например, std::list в C++, ArrayList в Java, list в Python). Для графа с \( n \) вершинами создаётся массив adj[n], где adj[i] — список смежных вершин для вершины с индексом \( i \).
Пример на Python для неориентированного графа без весов:
```python
Граф: 0-1, 0-2, 1-2, 1-3
n = 4 adj = [[] for _ in range(n)] edges = [(0, 1), (0, 2), (1, 2), (1, 3)] for u, v in edges: adj[u].append(v) adj[v].append(u)
Результат: adj = [[1, 2], [0, 2, 3], [0, 1], [1]]
```
Связный список
В некоторых реализациях (особенно на языках низкого уровня, таких как C) используется массив указателей на связные списки. Каждый узел списка содержит номер смежной вершины и, при необходимости, вес ребра, а также указатель на следующий элемент.
Динамические массивы
В современных языках часто применяются динамические массивы (например, vector<vector<int>> в C++ или List<List<Integer>> в Java), которые обеспечивают быстрый доступ по индексу и эффективное добавление элементов.
Словарь списков
В языках с поддержкой ассоциативных массивов (например, Python, JavaScript) можно использовать словарь, где ключами являются вершины, а значениями — списки смежных вершин. Это удобно для разреженных графов с произвольными (не обязательно целочисленными) идентификаторами вершин.
Сравнение с матрицей смежности
Список смежности и матрица смежности — два основных способа представления графов. Их выбор зависит от плотности графа и выполняемых операций.
| Характеристика | Список смежности | Матрица смежности | ||||||
|---|---|---|---|---|---|---|---|---|
| Объём памяти | \( O( | V | + | E | ) \) | \( O( | V | ^2) \) |
| Проверка наличия ребра | \( O(\deg(v)) \) в среднем, в худшем случае \( O( | V | ) \) | \( O(1) \) | ||||
| Перебор всех смежных вершин | \( O(\deg(v)) \) | \( O( | V | ) \) | ||||
| Добавление ребра | \( O(1) \) (амортизированно) | \( O(1) \) | ||||||
| Удаление ребра | \( O(\deg(v)) \) | \( O(1) \) | ||||||
| Удаление вершины | \( O( | E | ) \) в худшем случае | \( O( | V | ^2) \) |
Список смежности эффективнее по памяти для разреженных графов (где \( |E| \ll |V|^2 \)), которые часто встречаются на практике. Матрица смежности предпочтительнее для плотных графов или когда требуется часто проверять наличие конкретного ребра.
Модификации и расширения
Список смежности для мультиграфов
В мультиграфах, где между двумя вершинами может быть несколько рёбер, список смежности может содержать повторяющиеся записи. Для учёта кратности рёбер можно хранить не просто вершины, а пары (вершина, количество рёбер) или списки идентификаторов рёбер.
Список смежности с обратными рёбрами
Для ориентированных графов часто дополнительно хранят список обратных рёбер (транспонированный граф), что ускоряет некоторые алгоритмы, например, поиск сильно связанных компонент (алгоритм Косарайю).
Список смежности с дополнительной информацией
В списке смежности можно хранить не только смежные вершины, но и дополнительные данные о ребре: пропускную способность (для алгоритмов поиска максимального потока), стоимость (для алгоритмов поиска кратчайшего пути), метку времени и т.д.
Применение в алгоритмах
Список смежности является основой для многих классических алгоритмов на графах.
Поиск в ширину (BFS)
Алгоритм BFS обходит граф по уровням, используя очередь. Список смежности позволяет эффективно получать всех соседей текущей вершины, что даёт временную сложность \( O(|V| + |E|) \).
Поиск в глубину (DFS)
Алгоритм DFS использует стек (явный или рекурсию) для обхода графа. Список смежности также обеспечивает линейную сложность \( O(|V| + |E|) \).
Алгоритм Дейкстры
При реализации алгоритма Дейкстры с помощью очереди с приоритетами (кучи) список смежности позволяет быстро перебирать соседей каждой вершины. Временная сложность составляет \( O((|V| + |E|) \log |V|) \) при использовании двоичной кучи.
Алгоритм Прима
Алгоритм Прима для нахождения минимального остовного дерева также эффективно использует список смежности, особенно в сочетании с кучей, достигая сложности \( O((|V| + |E|) \log |V|) \).
Примеры использования
Представление карты дорог
Карта дорог между городами является классическим примером взвешенного графа. Каждый город — вершина, дорога — ребро с весом, равным расстоянию или времени в пути. Список смежности для такого графа будет содержать для каждого города список соседних городов и расстояний до них.
Социальные сети
Социальные сети (например, «ВКонтакте» или «Одноклассники» — зарегистрированные в РФ социальные сети) моделируются графами, где вершины — пользователи, а рёбра — дружеские связи. Список смежности для такого графа содержит для каждого пользователя список его друзей. Для графа социальной сети характерна разреженность, что делает список смежности оптимальным выбором.
Компьютерные сети
Топология компьютерной сети (например, соединения между маршрутизаторами) может быть представлена графом. Список смежности используется для моделирования маршрутов и расчёта оптимальных путей передачи данных.
Ограничения и недостатки
- Проверка наличия ребра: в отличие от матрицы смежности, проверка существования ребра между двумя вершинами может потребовать \( O(\deg(v)) \) времени, что неэффективно для плотных графов.
- Удаление ребра: удаление ребра из списка смежности может быть затратным, особенно если список реализован как массив, так как требует поиска элемента.
- Кэш-неэффективность: при использовании связных списков или разреженных динамических массивов элементы могут быть разбросаны в памяти, что снижает производительность из-за промахов кэша процессора.
- Сложность реализации некоторых операций: например, удаление вершины может потребовать обхода всех списков для удаления ссылок на неё.
Источники
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
- Седжвик Р., Уэйн К. Алгоритмы на Java. — 4-е изд. — М.: Вильямс, 2016. — 848 с.
- Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Вильямс, 2000. — 384 с.
- Окулов С. М. Программирование в алгоритмах. — М.: БИНОМ. Лаборатория знаний, 2014. — 383 с.
- ГОСТ Р 51904-2002 (IEEE Std 830-1998). Рекомендации по управлению программными проектами. (Раздел, касающийся структур данных).
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →