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

Определение 9.7. Пусть G=(V,E) - ориентированный граф, v - вершина из V. Список смежности L_v для вершины v включает все смежные с ней вершины, т.е.

Представление графа G=(V,E) c n вершинами V= { v₁, …, v_n} с помощью списков смежности состоит из списков смежности всех вершин: L_v1, L_v2, …, L_vn.

Размер этого представления сравним с суммой числа вершин и ребер графа. Оно позволяет легко переходить по ребрам от вершины к ее соседям. В программах списки смежностипредставляются списковыми структурами, которые легко реализуются во всех языках программирования.

Пример 9.1. Рассмотрим следующий граф G=(V,E):

Он показан на рис. 9.2.

Построим для него определенные выше представления.

1. Матрица смежности.

1. Матрица инцидентности.

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