1632
правки
Изменения
м
{{nohate}}
<br><br>
<br>
<br><br>
<br>
rollbackEdits.php mass rollback
'''Алгоритм двух китайцев''' — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.
=== Описание ===
Если хотя бы одна вершина графа <tex>G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br><br>
{|
|-
|
|}
=== Пример ===
{|class = "wikitable" width="70%" align="center"|-! Описание !! Изображение
|-
|Исходный граф.
=== Корректность ===
''' Замечания: '''
Из сделанных замечаний и леммы следует, что дерево <tex>T'</tex> — MST в <tex>G</tex>.
=== Реализация ===
Обозначения:
*Граф хранится в виде множества ребер + индекс корня.
int findMST(edges, n, root):
int result res = 0
int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью.
for each <tex>e \in E</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 E</tex>edges
if e.w == minEdge[e.to]
zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to
newComponents = Сondensation(zeroEdges)
edge newEdges[] //создаем массив ребер в новом графе с вершинами в полученных компонентах
for each <tex>e \in</tex> zeroEdgesedges
if e.to и e.from в разных компонентах
добавляем в newEdges ребро с концами в данных компонентах и весом e.w- minEdge[e.to] res += findMST(zeroEdgesnewEdges, ComponentsCount, newComponents[root])
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 Визуализатор алгоритма]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
