Изменения

Перейти к: навигация, поиск

Алгоритм Краскала

434 байта убрано, 20:55, 14 ноября 2014
Реализация
<tex>\mathtt{Unite}(v, u)\ </tex>
Очевидно, что максимальное ребро в MST минимально. Пусть мы построили алгоритмом Краскала минимальное остовное дерево и его максимальное ребро не минимально. Иначе говоря, в разрезе, который пересекает максимальное ребро, есть ребро с меньшим весом, но это противоречит тому, что алгоритм Краскала строит MST. Аналогично в максимальном остовном дереве минимальное ребро максимально. Такое дерево можно построить, заменив веса ребер на значения с противоположным знаком и запустив алгоритм поиска MST. В конце нужно не забыть снова поменять знаки.
==Пример==
Анонимный участник

Навигация