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

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

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

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

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

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

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

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

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

Ссылки

Гвидо ван Россум. Python Patterns — Implementing Graphs (неопр.) (1998).
Multimap at guava (неопр.).
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms, Second Edition (англ.). — MIT Press and McGraw-Hill, 2001. — P. 527—529 of section 22.1: Representations of graphs. — ISBN 0-262-03293-7.
Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples (англ.). — John Wiley & Sons, 2002. — ISBN 0-471-38365-1.
Steven Skiena Тhe Algorithm Design Manual (2nd ed.) (неопр.). — 2010. — С. 152 of section 5.2: Data Structures for Graphs. — ISBN 0-387-00163-8.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Гвидо ван Россум. Python Patterns — Implementing Graphs (неопр.) (1998).

[2] Multimap at guava (неопр.).

[3] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms, Second Edition (англ.). — MIT Press and McGraw-Hill, 2001. — P. 527—529 of section 22.1: Representations of graphs. — ISBN 0-262-03293-7.

[A-4] Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples (англ.). — John Wiley & Sons, 2002. — ISBN 0-471-38365-1.

[5] Steven Skiena Тhe Algorithm Design Manual (2nd ed.) (неопр.). — 2010. — С. 152 of section 5.2: Data Structures for Graphs. — ISBN 0-387-00163-8.