Список смежности и матричное представление графа
Сара Чен
⚡ Умное резюме
В представлении графа в виде списка смежности и матрицы вершины и ребра хранятся в памяти, что позволяет алгоритмам перемещаться по сетям. Список смежности использует связанные списки для каждой вершины, тогда как матрица смежности использует квадратную двумерную сетку.
Хотя они выглядят по-разному, все типы графиков Их можно представить аналогичным образом. В целом, существует два типа представления графов:
- Матрица смежности
- Список смежности
Список смежности
Список смежности состоит из связанных списков. Каждая вершина рассматривается как индекс массива, а каждый элемент представляет собой связанный список. Эти связанные списки содержат вершины, имеющие общее ребро с вершиной, указанной в индексе.
Вот пример списка смежности:
Пусть граф содержит V вершин и E ребер. Пространственная сложность списка смежности равна O(V + E), которая масштабируется в зависимости от количества реальных ребер, а не от каждой возможной пары вершин.
В худшем случае пространственная сложность становится O(V²) Если данный граф является полным, то каждая вершина соединяется с каждой другой вершиной.
Матрица смежности
Матрица смежности представляет собой двумерный массив. Для графа с V вершинами размер матрицы будет равен V × V.
Сказать matrix[i][j] = 5Это означает, что между узлом i и узлом j существует ребро с весом 5.
Рассмотрим следующий граф и его матрицу смежности:
Мы построили 2D массив используя эти шаги:
Шаг 1) Вершина А имеет прямое ребро с вершиной В, и вес ребра равен 5. Следовательно, ячейка в строке А и столбце В будет заполнена числом 5. Остальные ячейки в строке А будут заполнены числом ноль.
Шаг 2) Вершина B имеет прямое ребро с вершиной C, и вес этого ребра равен 4. Таким образом, ячейка в строке B и столбце C будет заполнена числом 4. Остальные ячейки в строке B будут заполнены нулевым числом, поскольку у вершины B нет исходящего ребра ни к одной другой вершине.
Шаг 3) Вершина C не имеет прямых ребер ни с одной другой вершиной. Поэтому строка C будет заполнена нулями.
Шаг 4) Вершина D имеет направленное ребро с вершинами A и C.
- В ячейке в строке D и столбце A будет значение 7. В ячейке в строке D и столбце C будет значение 2.
- Остальные ячейки строки D будут заполнены нулями.
Шаг 5) Вершина E имеет направленное ребро с вершинами B и D. Ячейка в строке E и столбце B будет иметь значение 6. Ячейка в строке E и столбце D будет иметь значение 3. Остальные ячейки в строке E будут заполнены нулями.
Вот некоторые моменты, на которые следует обратить внимание:
- Когда главная диагональ матрицы смежности равна 0, граф не имеет петель.
- Граф является ориентированным, если ячейки в точках (a, b) и (b, a) не принимают одинаковое значение. В противном случае граф является неориентированным.
- Граф является взвешенным, если значение любой ячейки больше 1.
Главная проблема матрицы смежности заключается в том, что она требует квадратного пространства. Даже несуществующие ребра все равно выделяют ячейки в памяти.
Например, если у нас есть граф со 100 узлами, то для его хранения потребуется 10 000 ячеек. Оперативная памятьПри меньшем количестве ребер в графе выделение такого большого объема памяти может быть неэффективным. Поэтому пространственная сложность при использовании матрицы смежности составляет O(N²)где N — количество узлов в графе.
Список смежности против матрицы смежности
Прежде чем выбирать способ представления данных, полезно сравнить обе модели параллельно по операциям, которые доминируют в реальных рабочих нагрузках на графах:
| Эксплуатация | Матрица смежности | Список смежности |
|---|---|---|
| Пространство сложности | О(В²) | O(V + E) |
| Добавить вершину | О(В²) | O (1) |
| Добавить край | O (1) | O (1) |
| Удалите край | O (1) | О (Э) |
| Проверьте, существует ли ребро (i, j). | O (1) | O(степень i) |
| Пройтись по соседям i | О (В) | O(степень i) |
| лучше всего для | Плотные графы, частые запросы к ребрам. | Разреженные графы, задачи, требующие интенсивного обхода графов. |
Вкратце, матрица смежности выигрывает по времени поиска ребер, в то время как список смежности выигрывает по памяти и количеству итераций по соседям, поэтому такие алгоритмы, как BFS, DFS и Дейкстра, обычно используются в паре со списками смежности.
Преимущества и недостатки графового представления
Каждый способ представления имеет свои компромиссы. Знание сильных и слабых сторон обеих моделей поможет вам выбрать ту, которая лучше всего подходит для решения вашей задачи.
Преимущества матрицы смежности:
- Запросы на существование ребер между любой парой вершин за постоянное время O(1).
- Фиксированная индексация упрощает реализацию матричных алгоритмов, таких как алгоритм Флойда-Уоршалла и алгоритм транзитивного замыкания.
- Взвешенные ребра естественным образом вписываются в единую матричную ячейку.
Недостатки матрицы смежности:
- Тратит O(V²) памяти, когда граф разреженный.
- Для добавления новой вершины необходимо изменить размер всей матрицы.
- Итерация по соседям одной вершины занимает O(V) даже тогда, когда у вершины всего несколько рёбер.
Преимущества списка смежности:
- Использует всего O(V + E) памяти, что близко к реальному количеству ребер в разреженных графах.
- Добавление новой вершины или ребра занимает O(1).
- Алгоритмы обхода, такие как BFS и DFS, перебирают соседей за O(степень), что в целом дает время выполнения O(V + E).
Недостатки списка смежности:
- Проверка существования конкретного ребра занимает время O(степени) вместо O(1).
- Локализация кэша слабее, поскольку связанные списки разбросаны по всей памяти.
- Для взвешенных ребер требуется дополнительное поле или список пар, что несколько усложняет структуру данных.
Когда использовать список смежности, а когда матрицу смежности?
Выбор способа представления зависит от плотности графа и наиболее часто выполняемых операций. Воспользуйтесь этим кратким руководством, чтобы выбрать подходящую структуру:
- Предпочтительнее использовать матрицу смежности. Когда граф плотный (E близко к V²), когда ребра редко меняются и когда ваш алгоритм многократно задает вопрос: «Есть ли ребро между i и j?».
- Предпочтительнее использовать список смежности. когда граф разреженный (E значительно меньше V²), когда множество вершин или ребер увеличивается во время выполнения, и когда вы обходите граф с помощью BFS, DFS или Алгоритм Дейкстры для поиска кратчайшего пути.
- Предпочтительна смешанная модель. (список смежности плюс хэш-множество ребер) когда вам нужна как быстрая итерация соседей, так и запросы ребер со сложностью O(1), ценой дополнительной памяти.
Современные библиотеки для работы с графами, такие как NetworkX и igraph, по умолчанию используют списки смежности, поскольку большинство реальных графов — социальные сети, дорожные карты, веб-страницы, зависимости пакетов — являются разреженными и требуют интенсивного обхода.
