В теории графов и информатике , список смежности представляет собой набор неупорядоченных списков , используемых для представления конечного графа . Каждый список описывает набор соседей вершины в графе. Это одно из нескольких часто используемых представлений графиков для использования в компьютерных программах.
Детали реализации [ править ]
| График, изображенный выше, имеет такое представление списка смежности: | ||
| а | рядом с | до н.э |
| б | рядом с | а, в |
| 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. Таким образом, граф должен быть достаточно разреженным, чтобы оправдать представление списка смежности.
Помимо экономии места, различные структуры данных также облегчают выполнение различных операций. Найти все вершины, смежные с данной вершиной в списке смежности, так же просто, как прочитать список. При использовании матрицы смежности вместо этого необходимо сканировать всю строку, что занимает время O (| V |) . Наличие ребра между двумя заданными вершинами можно определить сразу с помощью матрицы смежности, при этом потребуется время, пропорциональное минимальной степени двух вершин со списком смежности.
Ссылки [ править ]
- ↑ Гвидо ван Россум (1998). «Шаблоны Python - Реализация графиков» .
- ^ Томас Х. Кормен ; Чарльз Э. Лейзерсон ; Рональд Л. Ривест ; Клиффорд Стейн (2001). Введение в алгоритмы , второе издание . MIT Press и McGraw-Hill. С. 527–529 раздела 22.1: Представления графов. ISBN 0-262-03293-7.
- ^ Майкл Т. Гудрич и Роберто Тамассия (2002). Разработка алгоритмов: основы, анализ и примеры в Интернете . Джон Вили и сыновья. ISBN 0-471-38365-1.
Дальнейшее чтение [ править ]
- Дэвид Эппштейн (1996). «ICS 161 Lecture Notes: Graph Algorithms» .
Внешние ссылки [ править ]
 | Викискладе есть медиафайлы, связанные со списком смежности . |
- Библиотека Boost Graph реализует эффективный список смежности
- Структуры открытых данных, раздел 12.2, AdjacencyList: граф как набор списков , Пат Морин
