WikiSort.ru - Программирование

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

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

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

• Реализация, предложенная Гвидо ван Россумом, использует хеш-таблицу для ассоциации каждой вершины со списком смежных вершин. Нет явного представления рёбер в этой структуре^[1][2][3][4].
• Кормен и другие предложили реализацию, в которой вершины представлены числовым индексом в массиве, в котором каждая ячейка массива ссылается на однонаправленный связанный список соседних вершин.^[5]
• Объектно-ориентированный список смежности, предложенный Гудричем и Таммасией, содержит специальные классы вершин и рёбер. Каждый объект вершины содержит ссылку на коллекцию рёбер. Каждый объект ребра содержит ссылки на исходящую и входящую вершины.^[6]

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

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

Ссылки