Список смежности
 | Эта статья нуждается в дополнительных цитатах для проверки . ( сентябрь 2023 г. ) |
В теории графов и информатике список смежности представляет собой набор неупорядоченных списков, используемых для представления конечного графа . Каждый неупорядоченный список в списке смежности описывает набор соседей определенной вершины в графе. Это одно из нескольких часто используемых представлений графов для использования в компьютерных программах.
Детали реализации [ править ]
| График, изображенный выше, имеет такое представление списка смежности: | ||
| а | рядом с | б, в |
| б | рядом с | а, в |
| с | рядом с | а, б |
Представление списка смежности графа связывает каждую вершину графа с набором соседних вершин или ребер. Существует множество вариаций этой базовой идеи, отличающихся деталями того, как они реализуют связь между вершинами и коллекциями, тем, как они реализуют коллекции, включают ли они как вершины, так и ребра или только вершины в качестве объектов первого класса, и в чем они заключаются. типы объектов используются для представления вершин и ребер.
- Реализация, предложенная Гвидо ван Россумом, использует хеш-таблицу для связи каждой вершины графа с массивом соседних вершин. В этом представлении вершина может быть представлена любым хешируемым объектом. Не существует явного представления ребер как объектов. [1]
- Кормен и др. предложите реализацию, в которой вершины представлены индексными номерами. [2] В их представлении используется массив, индексированный по номеру вершины, в котором ячейка массива для каждой вершины указывает на односвязный список соседних вершин этой вершины. В этом представлении узлы односвязного списка можно интерпретировать как краевые объекты; однако они не хранят полную информацию о каждом ребре (они хранят только одну из двух конечных точек ребра), а в неориентированных графах для каждого ребра будет два разных узла связанного списка (по одному в списках для каждого из двух ребер). концы ребра).
- Объектно -ориентированная структура списка инцидентностей, предложенная Гудричем и Тамассией, имеет специальные классы вершинных объектов и реберных объектов. Каждый объект вершины имеет переменную экземпляра, указывающую на объект коллекции, в котором перечислены соседние объекты ребер. В свою очередь, каждый объект ребра указывает на два объекта вершины в своих конечных точках. [3] Эта версия списка смежности использует больше памяти, чем версия, в которой соседние вершины перечислены напрямую, но существование явных объектов ребер обеспечивает дополнительную гибкость при хранении дополнительной информации о ребрах.
Операции [ править ]
Основная операция, выполняемая структурой данных списка смежности, заключается в сообщении списка соседей данной вершины. Используя любую из описанных выше реализаций, это можно выполнить за постоянное время для каждого соседа. общее время сообщения обо всех соседях вершины v пропорционально степени v . Другими словами ,
Также возможно, но не так эффективно, использовать списки смежности для проверки наличия или отсутствия ребра между двумя заданными вершинами. В списке смежности, в котором соседи каждой вершины не отсортированы, проверка существования ребра может выполняться за время, пропорциональное минимальной степени двух заданных вершин, путем последовательного поиска по соседям этой вершины. Если соседи представлены в виде отсортированного массива, вместо этого можно использовать двоичный поиск , занимающий время, пропорциональное логарифму степени.
Компромиссы [ править ]
Основной альтернативой списку смежности является матрица смежности — матрица , строки и столбцы которой индексируются по вершинам, а ячейки содержат логическое значение, указывающее, присутствует ли ребро между вершинами, соответствующими строке и столбцу ячейки. Для разреженного графа (в котором большинство пар вершин не соединены ребрами) список смежности значительно более эффективен, чем матрица смежности (хранящаяся в виде двумерного массива): использование пространства списком смежности пропорционально количеству ребер и вершин в графе, а для хранимой таким образом матрицы смежности пространство пропорционально квадрату числа вершин. Однако можно хранить матрицы смежности более эффективно, используя линейное пространство в списке смежности, используя хеш-таблицу, индексированную парами вершин, а не массив.
Другое существенное различие между списками смежности и матрицами смежности заключается в эффективности выполняемых ими операций. В списке смежности соседи каждой вершины могут быть перечислены эффективно за время, пропорциональное степени вершины. В матрице смежности эта операция занимает время, пропорциональное количеству вершин в графе, которое может быть значительно больше степени. С другой стороны, матрица смежности позволяет проверить, являются ли две вершины смежными друг с другом за постоянное время; список смежности поддерживает эту операцию медленнее.
Структуры данных [ править ]
Для использования в качестве структуры данных основной альтернативой списку смежности является матрица смежности. Поскольку каждая запись в матрице смежности требует только одного бита, ее можно представить очень компактно, занимая всего | В | 2 /8 байт непрерывного пространства, где | В | — количество вершин графа. Эта компактность не только позволяет избежать бесполезного использования пространства, но и способствует локальности ссылок .
Однако для разреженного графа списки смежности требуют меньше места, поскольку они не тратят пространство для представления отсутствующих ребер. Используя простую реализацию массива на 32-битном компьютере, список смежности для неориентированного графа требует около 2⋅(32/8)| Е | = 8| Е | байт пространства, где | Е | — количество ребер графа.
Учитывая, что неориентированный простой граф может иметь не более (| V | 2 −| V |)/2 ≈ V 2 ребра, допускающие циклы, мы можем положить d = | Э |/| В | 2 обозначают плотность графа. Тогда 8| Е | > | В | 2 /8 когда | Э |/| В | 2 > 1/64 , то есть представление списка смежности занимает больше места, чем представление матрицы смежности, когда d > 1/64 . Таким образом, граф должен быть достаточно разреженным, чтобы оправдать представление списка смежности.
Помимо компромисса по пространству, различные структуры данных также облегчают выполнение различных операций. Найти все вершины, смежные с данной вершиной, в списке смежности так же просто, как прочитать список. При использовании матрицы смежности вместо этого необходимо сканировать всю строку, что занимает время O (| V |) . Существует ли ребро между двумя заданными вершинами, можно определить сразу с помощью матрицы смежности, при этом потребуется время, пропорциональное минимальной степени двух вершин с помощью списка смежности.
Ссылки [ править ]
- ^ ван Россум, Гвидо (1998). «Шаблоны Python — реализация графов» . Архивировано из оригинала 25 июня 2016 г. Проверено 17 августа 2014 г.
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). Введение в алгоритмы , второе издание . MIT Press и McGraw-Hill. стр. 527–529 раздела 22.1: Представления графов. ISBN 0-262-03293-7 .
- ^ Гудрич, Майкл Т .; Тамассия, Роберто (2002). Разработка алгоритмов: основы, анализ и примеры из Интернета . Джон Уайли и сыновья. ISBN 0-471-38365-1 .
Дальнейшее чтение [ править ]
Внешние ссылки [ править ]
- Библиотека Boost Graph реализует эффективный список смежности .
- Структуры открытых данных, раздел 12.2, AdjacencyList: граф как совокупность списков , Пэт Морин