Глава 17. Свойства и типы графов. функций не представляет каких-либо трудностей (см

функций не представляет каких-либо трудностей (см. упражнение 17.28), но в то же время на выполнение каждой такой операции может потребоваться время, пропорциональное К, которое затрачивается на поиск в списках узлов, представляющих эти ребра. Подоб­ные затраты делают представление графа в виде списка смежных вершин неприемлемым для приложений, выполняющих обработку особо крупных графов, по условиям которых наличие параллельных ребер исключается, или для приложений, в рамках которых интен­сивно используются операции remove edge (удалить ребро) или edge existence (проверка на­личия ребра). В разделе 17.5 мы будем обсуждать реализации списка смежных вершин, ко­торые обеспечивают выполнение операций remove edge и edge existence за постоянное время.

Когда в качестве имен вершин графа используются обозначения, отличные от целых чисел, то (как и в случае матриц смежности) две разные программы могут связывать име­на вершин с целыми числами в диапазоне от 0 до V— 1 двумя различными способами, приводящими к образованию двух различных структур списка смежных вершин (см., на­пример, программу 17.15). Мы не можем рассчитывать на то, что сумеем определить, пред­ставляют ли различные структуры один и тот же граф, ввиду сложности проблемы изо­морфизма графов.

Более того, существует множество представлений графа с заданным числом вершин в виде списков смежных вершин даже при заданной нумерации вершин. Не важно, в ка­ком порядке появляются ребра в списке смежных вершин, структура списка смежных вершин представляет один и тот же граф (см. упражнение 17.33). Полезно знать об этом свойстве списков смежных вершин, поскольку порядок, в котором ребра появляются в списках смежные вершины, влияет, в свою очередь, на порядок, в котором ребра обра­батываются алгоритмами. Это значит, что структура списка смежных вершин определя­ет, под каким углом зрения используемые нами алгоритмы видят сам граф. И хотя алго­ритм должен дать правильный ответ вне зависимости от того, в каком порядке расположены ребра в списке смежных вершин, он должен прийти к правильному отве­ту в условиях различных последовательностей вычислений, обусловленных различными видами упорядочения ребер. Если алгоритм не обязательно должен проверять все ребра, образующие граф, это обстоятельство может повлиять на продолжительность выполнения данной операции. Кроме того, если имеются несколько правильных решений, то различ­ные упорядочения входных данных могут привести к различным выходным результатам.

Основное преимущество представления графа в виде списка смежных вершин перед представлением в виде матрицы смежности заключается в том, что на его реализацию зат­рачивается пространство памяти, пропорциональное V + Е, а не V², как в случае пред­ставления в виде матрицы смежности. Основной недостаток этого представления состо­ит в том, что проверка существования конкретных ребер может потребовать времени, пропорционального V, в противовес постоянному времени в случае матрицы смежнос­ти. Эти различия приводят, главным образом, к различию в использовании связных спис­ков и векторов для представления множеств вершин, инцидентных каждой вершине.

Таким образом, мы снова убеждаемся в том, что понимание основных свойств связ­ных структур данных и векторов критично для построения реализаций АТД графа. Наш интерес к такому различию в производительности обусловливается тем фактом, что мы хотим избежать реализаций, эффективность которых падает до недопустимого уровня в условиях, когда от АТД требуется выполнение широкого спектра операций. В разделе 17.5