Вариации, расширения и затраты

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

Реализации, которые были построены в разделах 17.7 и 17.9, выполняют построение орграфов, если вызов конструктора содержит второй аргумент, значением которого яв­ляется true. Как показано на рис. 17.11, каждое ребро входит в представление графа толь­ко один раз. Ребро v-w в орграфе представлено единицей в элементе матрицы смежнос­ти, расположенном на пересечении строки v и столбца w или вершиной w в списке смежных вершин вершины v в представлении графа в виде множества списков смежных вершин. Эти представления проще, чем соответствующие представления, которые были выбраны для неориентированных графов, однако асимметрия, характерная для графов этого типа, делает их более сложными комбинаторными объектами, чем неориентирован­ные графы, в чем мы убедимся, ознакомившись с содержимым главы 19. Например, стан­дартное представление графа в виде списка его смежных вершин не обеспечивает воз­можности применять прямые методы выявления всех ребер, входящих в заданную вершину орграфа, и упомянутое обстоятельство вынуждает нас искать другие представ­ления графа в случаях, когда требуется поддержка этой операции.

Часть 5. Алгоритмы на графах

Что касается взвешенных графов (weighed graphs) и се­тей (networks), то мы наполняем матрицу смежности структурами, содержащими информацию о ребрах (включая данные об их наличии или отсутствии), заме­няя ими соответствующие булевские значения; в пред­ставлении графа в виде списков смежных вершин мы включаем эту информацию в элементы списков смеж­ных вершин.

Часто возникает необходимость привязывать к вер­шинам или ребрам графа еще больше информации, чтобы графы могли моделировать более сложные объек­ты. В качестве одного из возможных вариантов мы мо­жем ассоциировать дополнительную информацию с каждым ребром путем расширения типа Edge, употреб­ляемого в программе 17.1, с последующим использова­нием примеров этого типа в матрицах смежности или в узлах списков в списках смежных вершин. Или, по­скольку имена вершин суть целые числа в диапазоне от 0 до V— 1, мы можем воспользоваться векторами, ин­дексированными именами вершин, чтобы привязать к вершинам дополнительную информацию, возможно, с использованием соответствующих АТД. Мы будем рас­сматривать абстрактные типы данных (АТД) этого вида в главах 20-22. С другой стороны, мы можем восполь­зоваться отдельными АТД символьных таблиц для при­вязки дополнительной информации к каждой вершине и к каждому ребру (см. упражнение 17.48 и программу 17.15).

Чтобы успешно решать различные проблемы обра­ботки графов, мы часто определяем классы, которые содержат дополнительные специализированные струк­туры данных, связанные с графами. К числу наиболее распространенных структур данных такого рода отно­сятся векторы, индексированные именами вершин, как мы уже могли убедиться в главе 1, в которой мы вос­пользовались векторами, индексированными именами вершин, для ответа на запросы о связности графов. На протяжении данной книги мы используем векторы, ин­дексированные именами вершин, во многих реализаци­ях.

В качестве примера предположим, что мы хотим знать, является ли вершина v графа изолированной. Равна ли степень вершины v нулю? Что касается представления графа в виде списка смежных вершин, то мы находим эту информацию немедленно, просто про­верив, не равно ли значение adj[v] нулю. Однако для случая представления графа в виде матрицы смежности мы должны проверить все V элементов, соответствующих строке или