Объяснение алгоритма Крускала
Я читал википейду и нашел псевдокод Крускала следующим образом:
KRUSKAL(G):
foreach v ∈ G.V:
MAKE_SET(v)
G.E = sort(G.E)
i = 0
while (i != |V|-1):
pick the next (u, v) edge from sorted list of edges G.E
if (FIND_SET(u) != FIND_SET(v)):
UNION(u, v)
i = i + 1
Я не уверен, что FIND_SET() делает, и Википедия имеет следующее описание:
если этот край соединяет два разных дерева, то добавьте его в лес, объединив два дерева в одно дерево.
Так что я думаю, он проверяет, связаны ли два разных дерева, но что это на самом деле означает?
Решение
Первоначально каждая вершина находится в отдельном наборе: существует одноэлементное множество {v} для каждой вершины v, В псевдокоде эти наборы являются результатом make_set(v),
Для данной вершины v, функция find_set(v) дает вам набор, содержащий v,
Алгоритм объединяет множества итеративно, так что если {u}, {v} изначально одноэлементные множества и есть ребро (u, v), то алгоритм заменяет два набора их объединением {u, v}, Теперь оба find_set(u) а также find_set(v) вернет этот набор.
Алгоритм завершается после того, как вы добавили |V| - 1 нетривиальные ребра, которые в точности равны количеству ребер в дереве.
Другие решения
FIND_SET (x) находит набор, связанный с ребром x, так что сравнение:
FIND_SET(u) != FIND_SET(v)
Гарантирует, что u и v не связаны с одним и тем же. Полезный способ думать об этом состоит в том, что он находит «значения» u и v, где значения находятся в самих наборах.
Часть о слиянии лесов не имеет ничего общего с FIND_SET, а скорее следующая строка:
UNION(u,v)
Который объединяет два набора.
find_set() является обычной операцией типа структуры данных, известной как Union-Find. Идея этой структуры данных состоит в том, чтобы иметь непересекающиеся множества (вершины в вашем примере).
В этом алгоритме я думаю, что каждый набор представляет связную вершину.
Поэтому, когда вы звоните find_set() минуя вершину, вы получите элемент, представляющий этот набор связанных вершин.
find_set(u)!=find_set(v)
обозначает основное свойство связующего дерева, которое состоит в том, что оно не делает циклы. Если они равны, то это показывает, что в графе есть цикл.
Мы в основном создаем лес (с минимальными весами ребер) с помощью алгоритма Крускала и на каждом шаге проверяем, делает ли он цикл или нет.
Надеюсь, поможет 🙂