Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 17, Свойства и типы графов. adjIterator(const DenseGRAPH &G, int v)
|
|
public:
adjIterator(const DenseGRAPH & G, int v)
G(G), v(v), i(-l) { } int beg()
{ i = -1; return nxt(); } int nxt() {
for (i++; i < G.V(); i++)
if (G.adj[v][i] — true) return i; return -1; } bool end()
{ return i > = G.V(); } };
|
| Чтобы удалить ребро, мы присваиваем указанным элементам матрицы значение false. При попытке удалить несуществующее ребро (одно из тех, для которых значения соответствующих элементов матрицы есть false), программа не дает результата. Опять-таки, в некоторых проектах АТД мы можем посчитать целесообразным уведомлять клиентские программы о возникновении такого рода условий. Если мы выполняем разработку крупных графов или большое количество небольших по размерам графов, либо в тех случаях, когда по тем или иным причинам ощущается нехватка памяти, существует несколько способов экономии памяти. Например, матрицы смежности, которые служат представлением неориентированного графа, симметричны: элемент a[v][w] всегда равен элементу a [w][v]. Следовательно, мы можем сэкономить память, сохранив только половину симметричной матрицы (см. упражнение 17.22). Другой способ экономии значительного пространства памяти заключается в использовании матрицы битов (предполагая, что функция vector< bool> этого не делает). Таким образом, |
например, мы можем получить представление графа, состоящего примерно из 64000 вершин в примерно 64 миллионах 64-битовых слов (см. упражнение 17.23). Эти реализации связаны с небольшими осложнениями, поскольку нам необходимо добавить операцию по проверке существования ребра (см. упражнение 17.20). (Мы не используем такой операции в наших реализациях, поскольку можем проверить, существует ли ребро v-w путем проверки значения a[v][w]). Подобные методы экономии пространства памяти эффективны, но их осуществление связано с дополнительными непроизводительными затратами ресурсов, которые могут пагубно сказаться на внутреннем цикле приложения, критического по времени выполнения.
Многие приложения привязывают к каждому ребру различную информацию — в таких случаях мы можем придать матрице смежности более универсальный характер, позволив ей хранить любую информацию, а не только булевские значения. Какой бы тип данных мы не использовали для представления элементов матрицы,
РИСУНОК 17.9. СТРУКТУРА ДАННЫХ МАТРИЦЫ СМЕЖНОСТИ
На этом рисунке изображено C++-представление графа, показанного на рис. 17.1, в виде вектора векторов.
Часть 5. Алгоритмы на графах
все равно необходимо включить признаки, указывающие, существует ли соответствующее ребро или нет. В главах 20 и 21 мы проведем исследование таких представлений.
Использование матриц смежности зависит от назначения в качестве имен вершин целых чисел в диапазоне от 0 до V— \. Подобного рода назначения можно выполнять множеством различных способов; в качестве примера, в разделе 17.6 мы рассмотрим программу, которая выполняет эту процедуру. Таким образом, конкретная матрица значений 0-1, которую мы представили в виде вектора векторов в языке C++, не является единственным возможным представлением заданного графа в виде матрицы смежности, ибо другая программа может присвоить другие имена вершин индексам, которые мы используем для обозначения строк и столбцов. Две матрицы, которые на первый взгляд существенно отличаются друг от друга, на самом деле могут представлять один и тот же граф (см. упражнение 17.17). Это замечание может быть использовано как одна из формулировок проблемы изоморфизма графа: несмотря на то, что мы хотели бы знать, являются ли две различные матрицы представлением одного и того же графа, еще никто не изобрел алгоритма, который всегда бы мог эффективно решать эту задачу. Эта трудность носит фундаментальный характер. Например, наши возможности найти эффективное решение различных важных проблем обработки графов полностью зависят от способа нумерации вершин (смотрите, например, упражнение 17.26).
Программа 17.3, которую мы рассматривали в разделе 17.2, распечатывает таблицу вершин, смежных с каждой конкретной вершиной. Когда она используется совместно с реализацией в программе 17.7, она распечатывает список вершин в порядке возрастания их индекса, как это сделано на рис. 17.7. Обратите, однако, внимание на тот факт, что она не является составной частью определения класса adjlterator, что она совершает обход вершин в порядке возрастания индексов, посему разработка клиента АТД, который производит распечатку представления графа в виде матрицы смежности — отнюдь не тривиальная задача (см. упражнение 17.18). Выходные данные, порождаемые этими программами, сами являются представлениями графа, служащими наглядной иллюстрацией выводов, к которым мы пришли, взяв в качестве основного критерия производительность алгоритма. Для печати такой матрицы потребуется пространство на странице, достаточное для размещения всех V2 элементов; чтобы распечатать списки, нужно пространство, достаточное для размещения V+E чисел. В случае разреженных графов, когда V2 огромно по сравнению с V+E, мы предпочитаем воспользоваться списками, а в случае насыщенного графа, когда Е и V2 сравнимы, — матрицей. Нам вскоре представится возможность убедиться в том, что мы придем к тем же выводам, когда будем сравнивать представление графа в виде матрицы смежности и его основной альтернативой — явным представлением графа в виде списков.
Представление графа в виде матрицы смежности не особенно подходит для разреженных графов: нам необходимо V2 битов памяти и выполнить V2 действий, чтобы построить такое представление. В насыщенном графе, в котором число ребер (число единичных битов в матрице) пропорционально V2, такая цена может быть приемлемой, поскольку для обработки ребер понадобится время, пропорциональное К2, независимо от того, какое представление используется. В случае разреженного графа, однако, именно инициализация матрицы может оказаться доминирующей составляющей времени выполнения алгоритма. Более того, может случиться так, что нам не хватит пространства для разме-