234
правки
Изменения
Нет описания правки
|
|}
<br>
<br>
=== Пример ===
{|width="70%" align="center"
|-
|Исходный граф.
|[[Файл:китайГраф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]]
|}
=== Корректность ===
*Романовский И. В. '''Дискретный анализ''', 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - '''ISBN 5-7940-0114-3'''
* [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
