На этом шаге мы приведем общие сведения о структурах смежности.
Пусть G - помеченный граф порядка N, V={1,2,...,N}, имеющий M рёбер.
- Определение.
- Структурой смежности (в программировании) называется способ представления графа в виде массива пар смежных вершин, при этом:
- (1) пара <x,y> соответствует ребру {x,y}, если граф является неориентированным;
- (2) пара <x,y> соответствует дуге <x,y>, если граф является ориентированным.
Пример. Приведём два массива рёбер A[] и B[], позволяющие моделировать в программировании следующие графы:
Рис.1. Примеры неорентированного и ориентированного графов
Объём памяти, требуемой для размещения этой структуры составляет 2 × M.
Метод представления графа с помощью структур смежности является экономным в отношении памяти (особенно в случае неплотных графов, когда M гораздо меньше N × N).
Неудобством представления графа в виде структур смежности является большое число шагов (порядка M в худшем случае), необходимое для получения множества вершин, к которым ведут ребра (дуги) из данной вершины.
Замечание (важное). Ситуацию можно значительно улучшить, упорядочив множество пар лексикографически и применяя двоичный поиск.
На следующем шаге мы рассмотрим списки инцидентности.
