ВУЗ:
Составители:
Рубрика:
38
ставляют граф, имеющий один или несколько компонентов связ-
ности. Множество вершин, принадлежащих отдельному компо-
ненту связности, для краткости будем называть “букетом”. Неко-
торое ребро образует цикл с ребрами, уже включенными в дерево,
если обе его концевые вершины принадлежат одному и тому же
компоненту связности (одному и тому же букету).
Работа алгоритма по построению покрывающего дерева закан-
чивается, когда количество ребер, окрашенных в синий цвет, ста-
новится равным числу, на единицу меньшему числа вершин графа,
или, что то же самое, когда все вершины графа оказываются в од-
ном букете.
Оба условия выхода относятся к случаю, когда исходный граф
содержит покрывающее дерево, то есть является связным.
Если граф не является связным, то алгоритм заканчивается по-
сле раскраски всех ребер графа. Голубые ребра образуют покры-
вающий лес. Число деревьев в полученном лесе равно числу буке-
тов.
Алгоритм Краскала
построения покрывающего дерева.
Начальная установка. Все ребра исходного графа являются неок-
рашенными и ни один из букетов не сформирован.
Шаг 1. Выбрать любое ребро, не являющееся петлей. Окрасить это
ребро в синий цвет и сформировать букет, включив в него
концевые вершины выбранного ребра.
Шаг 2. Выбрать любое неокрашенное ребро, которое не является
петлей. Если в графе такого ребра не найдется, то закончить
процедуру: исходный граф не содержит покрывающего дере-
ва.
После указанного выбора возможны четыре различных слу-
чая:
А. Обе концевые вершины выбранного ребра принадлежат
одному и тому же букету. В этом случае ребро окрашивается в
оранжевый цвет и производится возврат к началу шага 2.
Б. Одна из концевых вершин выбранного ребра принадлежит
некоторому букету, а другая концевая вершина не принадле-
жит ни одному из уже сформированных букетов. В этом слу-
чае выбранное ребро окрашивается в синий цвет и его конце-
вая вершина, не принадлежащая ранее ни одному букету,
включается в букет, которому принадлежит другая концевая
вершина рассматриваемого ребра.
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
