45
правок
Изменения
→Псевдокод
По каждому ребру пройдём один раз, для поиска максимального, займёт <tex>O(N)</tex>.<br>Работа с СНМ займет <tex>O(N\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>В результате получаем алгоритм работающий за линейное время <tex>O(N)</tex>.
=== Псевдокод ===
Все рёбра графа будем хранить в списке <tex>e</tex>, а рёбра остовного дерева в списке <tex>tree</tex>.<br>
В каждом ребре <tex>Edge</tex> храним следующую информацию:
* <tex>from, to</tex> {{---}} соединяемые вершины
* <tex>cost</tex> {{---}} вес ребра
<code>
'''functionbool''' ifMBST('''Edge'''[] e, '''Edge'''[] tree): '''int''' united = 0, <font color=green>// Сколько вершин мы объединили</font> '''int''' maxEdge = -Inf<tex>\infty</tex> '''for''' i = 1 '''to ''' tree.size maxEdge = max(maxEdge, tree[i].cost) <font color=green>// Поиск максимального ребра в дереве</font> '''for''' i = 1 '''to ''' n '''if''' e[i].cost >= maxEdge <font color=green>// Не соединяем вершины, если ребро не меньше максимального</font>
'''continue'''
'''if''' find(e[i].from]) != find(e[i].to) <font color=green>// Объединяем вершины, если они в разных множествах</font>
united++
unite(e[i].from,e[i].to)
'''if''' united == e.size - 1 <font color=green>// Дерево подходит, если в результате мы соединили все вершины</font> '''return''''' true''
'''else'''
'''return''''' false''
</code>
==Cм. также==
*[[Алгоритм Краскала]]
