Список смежности

Список смежности — один из способов представления графа в виде коллекции списков вершин. Каждой вершине графа соответствует список, состоящий из «соседей» этой вершины.

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

Особенности реализацииПравить

Граф на картинке наверху имеет следующий список смежности:
a	смежно к	b, c
b	смежно к	a, c
c	смежно к	a, b

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

• Реализация, предложенная Гвидо ван Россумом, использует хеш-таблицу для ассоциации каждой вершины со списком смежных вершин. Нет явного представления рёбер в этой структуре.
• Кормен и другие предложили реализацию, в которой вершины представлены числовым индексом в массиве, в котором каждая ячейка массива ссылается на однонаправленный связанный список соседних вершин.
• Объектно-ориентированный список смежности, предложенный Гудричем  (англ.) (рус. и Тамассией  (англ.) (рус., содержит специальные классы вершин и рёбер. Каждый объект вершины содержит ссылку на коллекцию рёбер. Каждый объект ребра содержит ссылки на исходящую и входящую вершины.

Сравнение с матрицей смежностиПравить

Основной источник:

Сравнение с матрицей смежности
Операция	Список смежности	Матрица смежности
Проверка на наличие ребра (x,y)	$O(|V|)$$O(|V|)$	$O(1)$$O(1)$
Определение степени вершины	$O(1)$$O(1)$	$O(|V|)$$O(|V|)$
Использование памяти для разреженных графов	$O(|V|+|E|)$$O(|V|+|E|)$	$O(|V{|}^2)$$O(|V|^{2})$
Вставка/удаление грани	$O(1)$$O(1)$	$O(d)$$O(d)$
Обход графа	$O(|V|+|E|)$$O(|V|+|E|)$	$O(|V{|}^2)$$O(|V|^{2})$