АЛГОРИТМЫПОИСКА ОСТОВА ГРАФА
Понятия и определения
Деревом называется произвольный неориентированный связный граф без циклов. Для произвольного связного неориентированного графа G = á V, Е ñ каждое деревоá V, Т ñ, где Т Í Е, будем называть остовом или стягивающим деревом графа G. Ребра такого дерева будем называть ветвями, а все остальные ребра графа будем называть хордами.
Отметим, что каждое дерево с n вершинами имеет n -1 ребер.
Использование алгоритма поиска в глубину
Процедуры поиска в глубину и в ширину можно простым способом использовать для нахождения стягивающих деревьев. В обоих случаях достижение новой вершины u из вершины v вызывает включение в дерево ребра { v, u }.
Алгоритм 4.1. Нахождение стягивающего дерева связного графа методом поиска в глубину.
Исходные данные: Связный граф G = á V, Е ñ, заданный соответствиями G [ v ], v Î V.
Результаты: Стягивающее дерево á V, Т ñ графа G.
procedure WGD (v);
(*прохождение в глубину и нахождение ребер дерева; переменные new, G, Т - глобальные *)
Begin
new [ v ]:= ложь;
for u Î G [ v ] do
if new [ u ] then (* { v, u } - новая ветвь *) begin
T:= T È { v, u }; WGD (u)
End
end; (* WGD *)
begin (* главная программа *)
for u Î V do new [ u ]:= истина; (*инициализация*)
T:=Æ; (* Т = множество найденных к этому моменту ветвей *)
WGD (r) (* r - произвольная вершина графа*)
End.
Вычислительная сложность алгоритма есть, очевидно, O (n+m), т.е. того же порядка, что и при поиске в глубину. Пример стягивающего дерева, построенного алгоритмом 4.1, приведен на рис. 4.1,а. Ветви дерева выделены жирными линиями.
 |
Рис. 4.1. Стягивающие деревья, построенные с помощью алгоритма 4.1 (а) и алгоритма 4.2 (б).
Использование алгоритма обхода в ширину
Подобным же способом можно построить стягивающее дерево, используя метод поиска в ширину.
Алгоритм 4.2. Нахождение стягивающего дерева связного графа методом поиска в ширину.
Исходные данные: Связный граф G= á V, Е ñ, представленный соответствиями G [ v ], v Î V.
Результаты: Стягивающее деревоá V, Т ñ графа G
Begin
for u Î V do new [ u ]:= истина; (* инициализация *)
T:=Æ; (* T -множество найденных к этому моменту ветвей*)
ОЧЕРЕДЬ = Æ; ОЧЕРЕДЬ Ü r;
new [ r ]:= ложь; (* r -корень стягивающего дерева *)
while ОЧЕРЕДЬ ¹ Æ do begin
v Ü ОЧЕРЕДЬ;
for u Î G [ v ] do
if new [ u ] then (* { v, u } = новая ветвь*) begin
ОЧЕРЕДЬ Ü u;
new [ u ]:= ложь;
T:= T È{ v, u }
End
End
End.
Данный алгоритм строит стягивающее дерево для неориентированного связного графа за O (m+n) шагов.
На рис. 4.1, б дан пример стягивающего дерева, построенного алгоритмом 4.2. Ветви его выделены на графе жирными линиями.
Изложенные результаты легко переносятся и на произвольные графы, не обязательно связные. Максимальный суграф без циклов произвольного графа G называется стягивающим лесом графа G, Очевидно, что стягивающий лес графа с k компонентами связности определяется через стягивающие деревья этих компонент и, следовательно, содержит n - k -1 ребер.
4.4. Лабораторная работа №4: “Поиск остова графа”
Цель работы:
Исследовать свойства достижимости и связности вершин в неориентированном графе, используя алгоритмы поиска стягивающего дерева в графе.
Задание:
Используя методические указания раздела 4 разработать исследовательскую программу поиска остовного дерева или леса в неориентированном графе от заданной вершины, используя один из алгоритмов поиска по выбранному варианту.
Варианты выполнения работы:
1) Использование рекурсивного алгоритма поиска в графе в глубину;
2) Использование нерекурсивного алгоритма поиска в графе в глубину;
3) Использование алгоритма поиска в графе в графе в ширину.
Порядок выполнения работы
Работа рассчитана на 2 часа. Составленная в результате исследовательская программа должна находить в заданном неориентированном графе следующие элементы:
· список вершин каждого остовного дерева в порядке его прохождения;
· список ребер в каждом остовном дереве.
В качестве тестов для отладки программы и решения исследовательских задач рекомендуем использовать следующие графы:
1) Связный неориентированный граф из 9 вершин, представленный на рис. 4.1.
2) Неориентированный граф с числом вершин не менее 12, состоящий из трех связных компонент. Этот граф выбрать самостоятельно.