Список смежности - Adjacency list

Этот неориентированный циклический граф можно описать тремя неупорядоченными списками {b, c }, {a, c }, {a, b }.

В теории графов и информатике , список смежности представляет собой набор неупорядоченных списков , используемых для представления конечного графа . Каждый неупорядоченный список в списке смежности описывает набор соседей конкретной вершины в графе. Это одно из нескольких часто используемых представлений графиков для использования в компьютерных программах.

Детали реализации

График, изображенный выше, имеет такое представление списка смежности:
а рядом с до н.э
б рядом с а, в
c рядом с а, б

Представление списка смежности для графа связывает каждую вершину в графе с набором ее соседних вершин или ребер. Существует множество вариантов этой базовой идеи, различающихся деталями того, как они реализуют связь между вершинами и коллекциями, тем, как они реализуют коллекции, включают ли они как вершины, так и ребра или только вершины в качестве объектов первого класса, и что типы объектов используются для представления вершин и ребер.

  • Реализация, предложенная Гвидо ван Россумом, использует хеш-таблицу для связывания каждой вершины в графе с массивом смежных вершин. В этом представлении вершина может быть представлена ​​любым хешируемым объектом. Нет явного представления ребер как объектов.
  • Cormen et al. предложить реализацию, в которой вершины представлены номерами индексов. Их представление использует массив, индексированный по номеру вершины, в котором ячейка массива для каждой вершины указывает на односвязный список соседних вершин этой вершины. В этом представлении узлы односвязного списка могут интерпретироваться как граничные объекты; однако они не хранят полную информацию о каждом ребре (они хранят только одну из двух конечных точек ребра), а в неориентированных графах будет два разных узла связанных списков для каждого ребра (по одному в списках для каждого из двух конечные точки края).
  • В объектно-ориентированной структуре списка инцидентности, предложенной Гудричем и Тамассией, есть специальные классы вершинных и граничных объектов. Каждый объект вершины имеет переменную экземпляра, указывающую на объект коллекции, в котором перечислены соседние граничные объекты. В свою очередь, каждый объект края указывает на два объекта вершины в своих конечных точках. Эта версия списка смежности использует больше памяти, чем версия, в которой смежные вершины перечислены напрямую, но наличие явных объектов ребер дает дополнительную гибкость при хранении дополнительной информации о ребрах.

Операции

Основная операция, выполняемая структурой данных списка смежности, заключается в сообщении списка соседей данной вершины. Используя любую из описанных выше реализаций, это может быть выполнено с постоянным временем для каждого соседа. Другими словами, общее время сообщать обо всех соседей вершины 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 |) . Существует ли край между двумя заданными вершинами, можно определить сразу с помощью матрицы смежности, при этом потребуется время, пропорциональное минимальной степени двух вершин со списком смежности.

использованная литература

дальнейшее чтение

внешние ссылки