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

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

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

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

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

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

• Реализация предложенная Гвидо ван Россумом использует хэш-таблицу для ассоциации каждой вершины со списком смежных вершин. Нет явного представления граней в этой структуре.

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

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

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