1632
правки
Изменения
м
rollbackEdits.php mass rollback
=== Описание ===
Если хотя бы одна вершина графа <tex>G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br><br>
{|
|-
|
|}
=== Пример ===
{| class = "wikitable" width="70%"
|-
! Описание !! Изображение
|-
|Исходный граф.
|[[Файл:китайГраф1.png|200px]]
|-
|Произведем спуск до нулевых ребер (Фаза 1, 2).
|[[Файл:китайГраф2.png|200px]]
|-
|По нулевым ребрам нельзя дойти до всех вершин из <tex>v</tex>, поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).
Найдем <tex>MST</tex> для данного графа.
|[[Файл:китайГраф3.png|200px]]
|-
|Произведем спуск до нулевых ребер (Фаза 1, 2).
|[[Файл:китайГраф4.png|200px]]
|-
|По нулевым ребрам нельзя дойти до всех вершин из <tex>v</tex>, поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).
Найдем <tex>MST</tex> для данного графа.
|[[Файл:китайГраф5.png|200px]]
|-
|Произведем спуск до нулевых ребер (Фаза 1, 2). По полученным нулевым ребрам можно дойти из корня до всех вершин. Тогда запускаем <tex>dfs</tex> из корня и возвращаем ребра.
|[[Файл:китайГраф6.png|200px]]
|-
|Находим корень в каждой из компонент, из каждого такого корня запускаем <tex>dfs</tex> по нулевым ребрам, возвращаем результат.
|[[Файл:китайГраф7.png|200px]]
|-
|Находим корень в каждой из компонент, из каждого такого корня запускаем <tex>dfs</tex> по нулевым ребрам. Полученое дерево и есть <tex>MST</tex> в исходном графе.
|[[Файл:китайГраф8.png|200px]]
|}
=== Корректность ===
''' Замечания: '''
* После перевзвешивания в каждую вершину, кроме <tex>v</tex>, входит по крайней мере одно ребро нулевого веса.<br>
* Пусть <tex>T</tex> — искомое дерево в <tex>G</tex> с весовой функцией <tex>w</tex>. <tex>w'(T) = w(T) - \sum \limits_{u \in V \setminus v}m(u)</tex>, т.е. <tex>T</tex> - MST в <tex>G</tex> с весовой функцией <tex>w</tex> тогда и только тогда, когда <tex>T</tex> — MST в <tex>G</tex> с весовой функцией <tex>w'</tex>.<br>
=== Реализация ===
Обозначения:*Граф хранится в виде множества ребер + индекс корня.*Множество ребер - список смежности.*Ребро - структура {from, to, weight}.*root - текущий корень. Особенность реализации: алгоритму не важна кратность ребер, поэтому при составлении нового графа кратные ребра могутпоявиться - это уменьшает асимптотику с <tex>O(V^2)</tex> до <tex>O(E)</tex> Проверяем, можно ли дойти из <tex>v</tex> до остальных вершин. Если можно - запускаем findMST. лолололint findMST(edges, n, root): int res = 0 int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью. for each <tex>e \in </tex> edges minEdge[e.to] = min(e.w, minEdge[e.to]) for each <tex>v \in V \backslash \{root\}</tex> res += minEdge[v] //веса минимальных ребер точно будут в результате edge zeroEdges[] //создаем массив нулевых ребер for each <tex>e \in </tex> edges if e.w == minEdge[e.to] zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to if dfs(root, zeroEdges) // проверяем, можно ли дойти до всех вершин по нулевым ребрам return res int newComponents[n] // будущие компоненты связности newComponents = Сondensation(zeroEdges) edge newEdges[] //создаем массив ребер в новом графе с вершинами в полученных компонентах for each <tex>e \in</tex> edges if e.to и e.from в разных компонентах цу добавляем в newEdges ребро с концами в данных компонентах и весом e.w - minEdge[e.to] вц res += findMST(newEdges, ComponentsCount, newComponents[root]) цв return res
=== Сложность ===
Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит, алгоритм можно реализовать за <tex>O(|V||E|VE)</tex>.
== Источники ==
* [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]
==См. также==* [[Алгоритм Борувки]]* [Файлhttp:graph1//en.png|thumb|right|300x200px|Исходный граф <tex>G<wikipedia.org/tex>]wiki/Edmonds%27_algorithm Edmonds' Algorithm]* [[Файлhttp:graph2//rain.ifmo.ru/cat/view.png|thumb|right|300x200px|Граф <tex>C<php/tex>, построенный по графу <tex>G<vis/tex>graph-spanning-trees/shortest-tree-chinese-2003 Визуализатор алгоритма]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
