Глава 20. Минимальные остовные деревья. которое ребро. Как и в случае матрицы смежности, мы можем при желании сэкономить пространство памяти

которое ребро. Как и в случае матрицы смежности, мы можем при желании сэкономить пространство памяти, поместив вершину назначения и вес в узел списка (оставляя неназ­ванной соответствующую вершину-источник) ценой усложнения итератора (см. упражне­ния 20.11 и 20.14).

На этом этапе полезно сравнить эти представления с простыми представлениями, о которых шла речь в начале этого раздела (см. упражнения 20.11 и 20.12). Если бы мы строили граф с нуля, то использование указателей потребовало бы гораздо большего про­странства памяти. Это пространство нужно не только для размещения указателей, но и для размещения индексов (имен вершин), которые в простых реализациях представлены неявно. Чтобы иметь возможность пользоваться указателями на ребра в представлении графа в виде матрицы смежности, требуется дополнительное пространство памяти для размещения V² указателей на ребра и Е пар индексов. Аналогично, чтобы иметь возмож­ность пользоваться указателями на ребра в условиях представления графа в виде списков смежных вершин, требуется дополнительное пространство памяти для размещения Е ука­зателей на ребра и Е индексов.

С другой стороны, использование указателей на ребра, по-видимому, позволит полу­чить более высокопроизводительный программный код, поскольку скомпилированный код клиентской программы использует указатель с тем, чтобы получить прямой доступ к весу соответствующего ребра, в отличие от простой реализации, в рамках которой тре­буется построить тип данных Edge (ребро) и получить доступ к его полям. Если стоимость требуемого пространства памяти непомерно высока, то применение минимальных пред­ставлений (и, возможно, выбор оптимальной организации итераторов с целью экономии времени) может оказаться разумной альтернативой; в противном случае, гибкость, обес­печиваемая применением указателей, по всем признакам, стоит дополнительных затрат памяти.

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

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

Как мы должны представить само дерево MST? Дерево MST графа G есть подграф графа G, который сам по себе является деревом, в связи с чем появляется множество ва­риантов, основными из которых являются:

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

РИСУНОК 20.3. ПРЕДСТАВЛЕНИЯ ВЗВЕШЕННОГО ГРАФА (НЕОРИЕНТИРОВАННОГО)

Два стандартных представления взвешенных неориентированных графов содержат веса в каждом представлении ребра, как видно из представлений графа, изображенного на рис. 20.1, в виде матрицы смежности (слева) и в виде списков смежных вершин (справа). Для простоты мы показываем веса на этих рисунках в элементах матрицы и в узлах списков; в наших программах мы используем указатели на ребра клиентов. Матрица смежности симметрична, а списки смежных вершин содержат два узла для каждого ребра, как и в случае невзвешенных ориентированных графов. Несуществующие ребра представлены в матрице нулевыми указателями (обозначены на рисунке звездочками) и в списках попросту отсутствуют. Петли отсутствуют в обоих показанных здесь представлениях, поскольку алгоритмы MTS без них оказываются проще, тогда как другие алгоритмы обработки взвешенных графов их используют (см. главу 21).

■ Граф.

■ Связный список ребер.

■ Вектор указателей на ребра.

■ Вектор, индексированный именами вершин с родительскими связями.

Рисунок 20.4 служит иллюстрацией перечисленных вариантов на примере дерева MST, изображенного на рис. 20.1. Другая альтернатива заключается в том, чтобы дать опреде­ление и использовать АТД для представления деревьев.

Одно и то же дерево допускает различные представления в любой из указанных выше схем. В каком порядке должны быть приведены ребра в представлении в виде списков ребер? Какой узел должен быть выбран в качестве корня в представлении в виде роди­тельских связей (см. упражнение 20.21)? По существу, во время выполнения алгоритма MST конкретное представление дерева MST, какое мы получаем при этом, есть артефакт используемого алгоритма и не отражает каких-либо важных свойств дерева MST.

Выбор того или иного представления дерева MST не оказывает заметного влияния на алгоритм, поскольку мы легко можем преобразовать каждое из этих представлений в лю­бое другое. Чтобы выполнить преобразование представления дерева MST в виде графа в вектор ребер, мы можем воспользоваться функцией GRAPHedges из программы 20.2. Чтобы преобразовать представление в виде родительских связей, зафиксированных в век­торе st (при этом веса представлены в векторе wt) в вектор mst указателей на ребра, вклю­ченные в дерево MST, можно воспользоваться циклом:

for (k = 1; к < G.V(); к++)

mst [к] = new EDGE (к, st [к], wt[k]);

Глава 20. Минимальные остовные деревья

РИСУНОК 20.4. ПРЕДСТАВЛЕНИЕ ДЕРЕВА MST

На этом рисунке показаны различные представления дерева MST, показанного на рис, 20.1. Наиболее простым из них является список его ребер, при этом какой-либо порядок отсутствует (диаграмма слева). К тому же изображенное дерево MST есть разреженный граф, и оно может быть представле­но в виде списков смежных вершин (диаграмма в центре). Наиболее компактным является представ­ление в виде родительских связей: в качестве корня мы выбираем одну из вершин и поддерживаем два вектора, индексированные именами вершин, в одном из них фиксируются родитель каждой вершины дерева, во втором указан вес ребра, ведущего из каждой вершины к ее родителю (диаграмма справа). Ориентация дерева (выбор корневой вершины) произвольна и не является свойством дерева MST. Мы можем выполнить преобразование любого из этих представлений в какое-либо другое за линейное время.

Этот программный код представляет типичный случай, когда в качестве корня дере­ва MST выбирается вершина 0, при этом он не помещает фиктивное ребро 0-0 в список ребер дерева MST.

Оба эти преобразования тривиальны, в то же время возникает вопрос, как выполня­ется преобразование представления дерева MST в виде вектора указателей на ребра в представление в виде родительских связей? В нашем распоряжении имеются базовые ин­струментальные средства, позволяющие с такой же легкостью решить и эту задачу: мы преобразуем указанное выше представление в граф, воспользовавшись циклом, подобным предложенному выше (измененным таким образом, что функция insert вызывается для каждого ребра), с последующим выполнением поиска в глубину из любой вершины с це­лью вычисления представления дерева DFS в виде родительских связей за линейное вре­мя.

Короче говоря, несмотря на то, что выбор представления дерева MST производится из соображений удобства, мы заключаем все наши алгоритмы в класс MST обработки графов, который вычисляет приватный вектор mst указателей на ребра. В зависимости от потребностей приложений, мы можем реализовать для этого класса функции-элементы, которые возвращают этот вектор или предоставляют клиентским программам другую ин­формацию о деревьях MST, однако мы не будем вдаваться в дальнейшие детали этого интерфейса, а отметим лишь, что в число инструментальных средств мы включаем фун­кцию-элемент show, которая вызывает аналогичную функцию для каждого ребра дерева MST (см. упражнение 20.8).