Список смежности
В теории графов и информатике список смежности представляет собой набор неупорядоченных списков, используемых для представления конечного графа . Каждый неупорядоченный список в списке смежности описывает набор соседей конкретной вершины в графе. Это одно из нескольких широко используемых представлений графов для использования в компьютерных программах.
Представление списка смежности для графа связывает каждую вершину графа с набором соседних вершин или ребер. Существует множество вариаций этой базовой идеи, различающихся деталями того, как они реализуют ассоциацию между вершинами и наборами, тем, как они реализуют наборы, включают ли они и вершины, и ребра, или только вершины в качестве объектов первого класса, и в чем они состоят. виды объектов используются для представления вершин и ребер.
Основная операция, выполняемая структурой данных списка смежности, состоит в том, чтобы сообщить список соседей данной вершины. Используя любую из описанных выше реализаций, это можно выполнить за постоянное время для каждого соседа. Другими словами, общее время сообщения обо всех соседях вершины v пропорционально степени v
Также возможно, но не так эффективно, использовать списки смежности для проверки существования или отсутствия ребра между двумя указанными вершинами. В списке смежности, в котором соседи каждой вершины не отсортированы, проверка на существование ребра может быть выполнена за время, пропорциональное минимальной степени двух заданных вершин, путем последовательного перебора соседей этой вершины. Если соседи представлены в виде отсортированного массива, вместо этого можно использовать двоичный поиск , требующий времени, пропорционального логарифму степени.
Основной альтернативой списку смежности является матрица смежности , матрица , строки и столбцы которой индексируются вершинами и чьи ячейки содержат логическое значение, указывающее, присутствует ли ребро между вершинами, соответствующими строке и столбцу ячейки. Для разреженного графа(тот, в котором большинство пар вершин не соединены ребрами) список смежности значительно более экономичен по пространству, чем матрица смежности (хранящаяся в виде двумерного массива): использование пространства списка смежности пропорционально количеству ребер и вершин в графе, в то время как для матрицы смежности, хранящейся таким образом, пространство пропорционально квадрату числа вершин. Однако можно хранить матрицы смежности более эффективно с точки зрения использования пространства, в соответствии с использованием линейного пространства списка смежности, используя хэш-таблицу, индексированную парами вершин, а не массивом.
Другое существенное различие между списками смежности и матрицами смежности заключается в эффективности выполняемых ими операций. В списке смежности соседи каждой вершины могут быть перечислены эффективно, за время, пропорциональное степени вершины. В матрице смежности эта операция занимает время, пропорциональное количеству вершин в графе, которое может быть значительно больше степени. С другой стороны, матрица смежности позволяет проверить, являются ли две вершины смежными друг с другом за постоянное время; список смежности медленнее поддерживает эту операцию.
