На этом шаге мы познакомимся с первым способом представления графов - списком ребер.
Знакомство со способами представления и обработки графов весьма поучительно. С одной стороны, графы являются достаточно наглядными объектами. С другой стороны, машинное представление графов допускает большое разнообразие. Сложность получения ответа на тот или иной вопрос относительно данного графа зависит, естественно, от способа представления графа. Поэтому в алгоритмах на графах взаимосвязь "алгоритм + структура данных" проявляется очень сильно. Один и тот же алгоритм, реализованный на различных структурах данных, очень часто приводит к совершенно разным программам.
Во многих задачах на графах выбор представления является решающим для повышения эффективности алгоритма. С другой стороны, переход от одного представления к другому относительно прост и может быть выполнен за O(|V|2) операций [1, с.355]. Поэтому если решение задачи на графе обязательно требует числа операций, по крайней мере пропорционального |V|2, то время ее решения не зависит от способа представления графа, так как оно может быть изменено за O(|V|2) операций.
Более экономным в отношении памяти (особенно в случае так называемых неплотных графов, когда |E| гораздо меньше |V|2) по сравнению с матрицей смежностей является метод представления графа с помощью структуры смежности, которая является в простейшем случае списком пар, соответствующих его ребрам [1, с.354].
Пара <x,y>, входящая в список ребер, соответствует ребру {x,y} в случае неориентированного графа и дуге (x,y), если граф ориентированный.
Например, приведем списки ребер, соответствующие неориентированным графам:
Рис.1. Примеры графов и списков ребер
Очевидно, что требуемый объем памяти в этом случае составляет 2|E|. Неудобством является большое число шагов (порядка |E| в худшем случае), необходимое для получения множества вершин, смежных данной вершине. Ясно, что при представлении графа в виде списка ребер, информация о вершинах может оказаться труднодоступной. Так будет в случае, когда число ребер намного больше числа вершин. Ситуацию можно значительно улучшить, если упорядочить множество пар лексикографически и применять при поиске нужного ребра (дуги) двоичный поиск, но лучшим решением во многих случаях оказывается структура данных, которая называется списками смежности.
(1) Рейнгольд Э., Нивергельт Ю., Део H. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.
На следующем шаге мы рассмотрим списки смежности.
