Определение остовных деревьев

Остовиым деревом (скелетом) неориентированного графа называется его подграф, не имеющий циклов и содержащий все вершины исходного графа. Так, например, для нагруженного графа, изображенного на рис. 9, а, скелетами являются все его подграфы, изображенные на рис. 9, б.

Рис. 9. Нагруженный неориентированный граф и его остовные поддеревья

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

Варианты скелетов исходного графа, изображенные на рис. 9, б, имеют различный суммарный вес ребер графа. В первом варианте сумма весов ребер скелета равна 15, во втором варианте— 27, и в третьем варианте— 19. В разных ситуациях бывает необходимо найти остовное дерево с максимальным или минимальным общим весом ребер. Так первое поддерево имеет минимальный суммарный вес из всех возможных поддеревьев. Второе поддерево— максимальный. Поставим задачу найти минимальное остовное дерево (т. е. остовное дерево минимального суммарного веса ребер) для заданного неориентированного графа. Разумеется, поиск максимального остовного дерева будет производиться по точно такому же алгоритму.

Первый из предлагаемых алгоритмов принадлежит классу так называемых жадных алгоритмов. Этот алгоритм пытается найти решение поставленной задачи в лоб, стараясь найти минимальное остовное дерево последовательным отбором ребер с минимальным весом, следя за тем, чтобы получающийся граф не имел циклов. Разумеется, для этого необходимо сначала отсортировать все ребра графа по возрастанию их весов. Лучше всего, если граф с самого начала представлен списком ребер, в этом случае сортировка будет наиболее естественной. Но даже и в других случаях сортировка ребер графа по весу занимает не слишком много времени— в худшем случае M x log2M, где М— количество ребер графа.

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

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

Рис. 10. а. Алгоритм Крускала построения минимального остовного дерева графа

 

Рис. 10. б. Алгоритм Крускала построения минимального остовного дерева графа

 

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

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

В листинге показана реализация алгоритма Крускала построения минимального остовного дерева. Метод minSkeieton графа получает в качестве аргумента выходной поток для печати в него информации о ребрах графа, включаемых в остовное дерево. Второй аргумент— это объект, задающий нагрузку на ребра графа. Информация о структуре минимального остовного дерева выводится в выходной поток в виде последовательности пар целых чисел — номеров вершин, задающих ребра графа, а общий полученный вес этого остовного дерева выдается в качестве результата работы функции.

На первом этапе работы алгоритма строится пирамида из ребер графа. В каждый узел пирамиды заносится информация о номерах соединяемых этим ребром вершин и о весе ребра. Информация о ребрах графа берется из матрицы смежности графа и объекта класса GraphWeight, задающего нагрузку на ребра.

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

Листинг: Реализация алгоритма Крускала построения минимального остовного дерева