1
правка
Изменения
м
<br><br>
<br>
<br><br>
<br> обозначенияОбозначения: *Граф хранится в виде множества ребер + индекс корня. *Множество ребер - список смежности. *Ребро - структура из трех чисел - {откуда реброfrom, куда реброto, вес ребраweight}. *root - текущий корень. Особенность реализации: алгоритму не важна кратность ребер, поэтому при составлении нового графа они кратные ребра могут появится появиться - это уменьшает асимптотику с <tex>O(V^2)</tex> до <tex>O(E)</tex>
<tex>int findMST(edges, n, root)</tex>: int result res = 0; int minEdge[n]; // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью. for each <tex>e \in E</tex>edges
<tex>if dfs(root, zeroEdges)</tex> // проверяем, можно ли дойти до всех вершин по нулевым ребрам if (можно дойти)
Исправление ошибки в псевдокоде
=== Описание ===
Если хотя бы одна вершина графа <tex>G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br><br>
{|
|-
|
|}
=== Пример ===
{|class = "wikitable" width="70%" align="center"|-! Описание !! Изображение
|-
|Исходный граф.
|[[Файл:китайГраф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>
Из сделанных замечаний и леммы следует, что дерево <tex>T'</tex> — MST в <tex>G</tex>.
=== Реализация ===
Проверяем, можно ли дойти из <tex>v</tex> до остальных вершин. Если можно - запускаем <tex>findMST</tex>.
minEdge[e.to] = min(e.w, minEdge[e.to])
for each <tex>v \in V, v != \backslash \{root\}</tex>
res += minEdge[v] //веса минимальных ребер точно будут в результате
edge zeroEdges[] //создаем массив нулевых ребер
for each <tex>e \in E</tex>edges if (текущее ребро равно по весу минимальному, входящему в эту вершину)e.w == minEdge[e.to]
zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to
return res
int newComponents[n]; // будущие компоненты связности newComponents = <tex>Сondensation(zeroEdges)</tex> edge newEdges[] //создаем массив ребер в новом графе с вершинами в сконденсированными компонентамиполученных компонентах for each <tex>e \in</tex> zeroEdgesedges if (концы e лежат .to и e.from в разных компонентах связности) добавляем в newEdges ребро с концами в данных компонентах и весом e.w- minEdge[e.to] res += <tex>findMST(zeroEdgesnewEdges, ComponentsCount, newComponents[root])</tex>
return res
* [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]
==См. также==
* [[Алгоритм Борувки]]
* [http://en.wikipedia.org/wiki/Edmonds%27_algorithm Edmonds' Algorithm]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/shortest-tree-chinese-2003 Визуализатор алгоритма]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
