Список смежности - Adjacency list
В теория графов и Информатика, список смежности представляет собой набор неупорядоченных списков, используемых для представления конечного график. Каждый список описывает набор соседей вершина в графике. Это одно из нескольких часто используемых представлений о графики для использования в компьютерных программах.
Детали реализации
| График, изображенный выше, имеет такое представление списка смежности: | ||
| а | рядом с | до н.э |
| б | рядом с | а, в |
| c | рядом с | а, б |
Представление списка смежности для графа связывает каждую вершину в графе с набором ее соседних вершин или ребер. Есть много вариантов этой базовой идеи, различающихся деталями того, как они реализуют связь между вершинами и коллекциями, тем, как они реализуют коллекции, включают ли они как вершины, так и ребра или только вершины в качестве объектов первого класса, и в чем типы объектов используются для представления вершин и ребер.
- Реализация, предложенная Гвидо ван Россум использует хеш-таблица связать каждую вершину в графе с массив смежных вершин. В этом представлении вершина может быть представлена любым хешируемым объектом. Нет явного представления ребер как объектов.[1]
- Cormen et al. предложить реализацию, в которой вершины представлены номерами индексов.[2] В их представлении используется массив, индексированный по номеру вершины, в котором ячейка массива для каждой вершины указывает на односвязный список из соседних вершин этой вершины. В этом представлении узлы односвязного списка могут интерпретироваться как граничные объекты; однако они не хранят полную информацию о каждом ребре (они хранят только одну из двух конечных точек ребра), а в неориентированных графах будет два разных узла связанных списков для каждого ребра (по одному в списках для каждого из двух конечные точки края).
- В объектно-ориентированный Структура списка инцидентности, предложенная Гудричем и Тамассией, имеет специальные классы вершинных объектов и граничных объектов. Каждый объект вершины имеет переменную экземпляра, указывающую на объект коллекции, в котором перечислены соседние граничные объекты. В свою очередь, каждый объект края указывает на два объекта вершины в своих конечных точках.[3] Эта версия списка смежности использует больше памяти, чем версия, в которой смежные вершины перечислены напрямую, но наличие явных краевых объектов дает дополнительную гибкость при хранении дополнительной информации о ребрах.
Операции
Основная операция, выполняемая структурой данных списка смежности, заключается в сообщении списка соседей данной вершины. Используя любую из описанных выше реализаций, это может быть выполнено с постоянным временем для каждого соседа. Другими словами, общее время, чтобы сообщить обо всех соседях вершины. v пропорционально степень из v.
Также возможно, но не так эффективно, использовать списки смежности для проверки того, существует ли ребро между двумя указанными вершинами. В списке смежности, в котором соседи каждой вершины не отсортированы, проверка существования ребра может быть выполнена за время, пропорциональное минимальной степени двух данных вершин, с использованием последовательный поиск через соседей этой вершины. Если соседи представлены в виде отсортированного массива, бинарный поиск Вместо этого можно использовать время, пропорциональное логарифму степени.
Компромиссы
Основной альтернативой списку смежности является матрица смежности, а матрица чьи строки и столбцы индексируются по вершинам, а ячейки содержат логическое значение, указывающее, присутствует ли ребро между вершинами, соответствующими строке и столбцу ячейки. Для разреженный граф (тот, в котором большинство пар вершин не соединены ребрами) список смежности значительно более эффективен по пространству, чем матрица смежности (хранящаяся как двумерный массив): использование пространства списком смежности пропорционально количеству ребер и вершин в графе, в то время как для матрицы смежности, хранящейся таким образом, пространство пропорционально квадрату количества вершин. Однако можно хранить матрицы смежности более эффективно по пространству, соответствуя линейному использованию пространства списком смежности, используя хэш-таблицу, индексированную парами вершин, а не массивом.
Другое существенное различие между списками смежности и матрицами смежности заключается в эффективности выполняемых ими операций. В списке смежности соседи каждой вершины могут быть перечислены эффективно, по времени, пропорциональному степени вершины. В матрице смежности эта операция занимает время, пропорциональное количеству вершин в графе, которое может быть значительно выше степени. С другой стороны, матрица смежности позволяет проверять, являются ли две вершины смежными друг с другом за постоянное время; список смежности медленнее поддерживает эту операцию.
Структуры данных
Для использования в качестве структуры данных основной альтернативой списку смежности является матрица смежности. Поскольку каждая запись в матрице смежности требует только одного бита, ее можно представить очень компактно, занимая только |V|2/8 байты непрерывного пространства, где |V| - количество вершин графа. Помимо экономии места, эта компактность способствует локализации ссылок.
Однако для разреженного графа списки смежности требуют меньше места, потому что они не тратят впустую пространство для представления ребер, которых нет. Используя простую реализацию массива на 32-битном компьютере, список смежности для неориентированного графа требует примерно 2·(32/8)|E| = 8|E| байты пространства, где |E| - количество ребер графа.
Отмечая, что неориентированный простой граф может иметь не более (|V|2-|V|)/2 ≈ V 2 края, позволяющие петли, мы можем позволить d = |E|/|V|2 обозначают плотность графика. Потом, 8|E| > |V|2/8 когда |E|/|V|2 > 1/64, то есть представление списка смежности занимает больше места, чем представление матрицы смежности, когда d > 1/64. Таким образом, граф должен быть достаточно разреженным, чтобы оправдать представление списка смежности.
Помимо экономии места, различные структуры данных также облегчают выполнение различных операций. Найти все вершины, смежные с данной вершиной в списке смежности, так же просто, как прочитать список. При использовании матрицы смежности вместо этого необходимо сканировать всю строку, что требует О(|V|) время. Наличие ребра между двумя заданными вершинами можно определить сразу с помощью матрицы смежности, при этом потребуется время, пропорциональное минимальной степени двух вершин со списком смежности.
использованная литература
- ^ Гвидо ван Россум (1998). "Шаблоны Python - реализация графиков".
- ^ Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Штайн (2001). Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill. С. 527–529 раздела 22.1: Представления графов. ISBN 0-262-03293-7.
- ^ Майкл Т. Гудрич и Роберто Тамассия (2002). Разработка алгоритмов: основы, анализ и примеры в Интернете. Джон Вили и сыновья. ISBN 0-471-38365-1.