Этот цикличный ненаправленный граф может быть описан тремя списками {b, c}, {a, c}, {a, b}.
Список смежности — один из способов представления графа в виде коллекции списков вершин. Каждой вершине графа соответствует список, состоящий из «соседей» этой вершины.
Граф на картинке наверху имеет следующий список смежности:
a
смежно к
b, c
b
смежно к
a, c
c
смежно к
a, b
Есть несколько вариаций представления графа списком смежности, отличающихся особенностями ассоциации вершин и коллекциями соседей, реализацией коллекций, включаются ли рёбра и вершины в коллекции соседей или только вершины, способами представления рёбер и вершин.
Реализация, предложенная Гвидо ван Россумом, использует хеш-таблицу для ассоциации каждой вершины со списком смежных вершин. Нет явного представления рёбер в этой структуре[1][2].
Кормен и другие предложили реализацию, в которой вершины представлены числовым индексом в массиве, в котором каждая ячейка массива ссылается на однонаправленный связанный список соседних вершин.[3]
Объектно-ориентированный список смежности, предложенный Гудричем[англ.] и Тамассией[англ.], содержит специальные классы вершин и рёбер. Каждый объект вершины содержит ссылку на коллекцию рёбер. Каждый объект ребра содержит ссылки на исходящую и входящую вершины.[4]
↑Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples (англ.). — John Wiley & Sons, 2002. — ISBN 0-471-38365-1.