Глава 17. Свойства и типы графов. чена проверка на возникновение ошибок по причине нехватки памяти - обычная практика предполагает включение подобного рода проверок

лено двумя вхождениями: ребро v-w представлено зна­чением true как для adj[v][w], так и для adj[w][v], что соответствует ребру w-v.

Имя DenseGRAPH в программе 17.7 подчеркивает тот факт, что рассматриваемая реализация больше подходит для насыщенных графов, чем для разрежен­ных, и отличает ее от других реализаций. Клиентская программа может воспользоваться определением типа typedef, чтобы сделать этот тип эквивалентным типу GRAPH или же явно воспользоваться именем DenseGRAPH.

В матрице смежности, которая представляет граф G, строка v есть вектор, представляющий собой табли­цу существования, i-e вхождение которого равно true, если i есть вершина, смежная с v (ребро v-i содержится в графе G). Следовательно, чтобы обеспечить клиен­там возможность обрабатывать вершины, смежные с v, необходима программа, которая просматривает этот вектор с целью нахождения значений true, как это де­лает программа 17.8. Мы должны всегда иметь в виду, что при использовании такая реализация обработки всех вершин, смежных с заданной вершиной, требует (по меньшей мере) время, пропорциональное числу вершин V графа, независимо от того, сколько таких вершин существует.

Как уже говорилось в разделе 17.2, наш интерфейс требует, чтобы в момент инициализации графа клиен­ту было известно число вершин. При необходимости мы могли бы обеспечить возможность добавления и удаления вершин (см. упражнение 17.21). Основное свойство конструктора в программе 17.7 заключается в том, что он выполняет инициализацию графа, уста­навливая значения false всем элементам матрицы. Мы должны иметь в виду, что эта операция требует для своего выполнения время, пропорциональное V², не­зависимо от того, сколько ребер в графе. Из сообра­жений краткости изложения в программу 17.7 не вклю-

РИСУНОК 17.8 ПРЕДСТАВЛЕНИЕ МАТРИЦЫ СМЕЖНОСТИ ГРАФА

Рассматриваемая булева матрица является еще одним представлением графа, показанного на рис. 17.1. В строке v и столбце w (true) этой матрицы стоит 1 (true), если в графе имеется ребро, соединяющее вершину v с вершиной w, и 0 (false), если такое ребро отсутствует. Эта матрица симметрична относитель­но главной диагонали. Например, шестая строка (и шестой столбец) показывает, что вершина б соедине­на с вершинами 0 и 4. Для некоторых приложений мы принимаем соглаше­ние, по условиям которого каждая вершина соединена сама с собой, и ставим единицы на главной диагона­ли. Большие области нулей в верхнем правом углу и нижнем левом углу матрицы обусловлены выбранным нами способом обозначения вершин для данного конкретного примера и не являются характеристиками рассматриваемого графика (за исключением того факта, что они указывают на принадлежность этого графа к категории разрежен­ных).

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