Алгоритм Крускалла не будет искать циклы, потому что он неэффективен;Но пытается создать компоненты дерева, а затем соединить их друг с другом.Как вы знаете, если вы соедините два разных дерева одним новым ребром, вы создадите новое дерево, и вам не нужно будет проверять циклы.
Если вы посмотрите на вики-страницу алгоритм выглядит следующим образом:
1. create a forest F (a set of trees), where each vertex in the graph is a separate tree
2. create a set S containing all the edges in the graph
3. while S is nonempty and F is not yet spanning
a. remove an edge with minimum weight from S
b. if that edge connects two different trees, then add it to the forest, combining
two trees into a single tree
c. otherwise discard that edge.
Для этого следует использовать Несвязанная структура данных набора .снова из вики:
сначала отсортируйте ребра по весу, используя сортировку сравнения по времени O (E log E);это позволяет этапу «удалить ребро с минимальным весом из S» работать в постоянном времени.Далее мы используем структуру данных с несвязным множеством (Union & Find), чтобы отслеживать, какие вершины и в каких компонентах.Нам нужно выполнить операции O (E), две операции поиска и, возможно, одно объединение для каждого ребра.Даже простая структура данных с несвязным множеством, такая как леса с несвязным множеством с объединением по рангу, может выполнять операции O (E) за время O (E log V).Таким образом, общее время O (E log E) = O (E log V).
Создание непересекающихся лесов
Теперь вы можете взглянуть на Boost Graph Library - Инкрементные компоненты часть.Вы должны реализовать несколько методов: MakeSet , Find , Union , после этого вы можете реализовать алгоритм Kruskall.Все, что вы делаете, это работаете с некоторыми наборами, и самый простой способ сделать это - использовать связанный список.
Каждый набор имеет один элемент с именем репрезентативный элемент , который является первым элементом в наборе.
1- Сначала внедрите MakeSet по связанным спискам:
Это подготавливает структуру данных несвязанных наборов для алгоритма инкрементных связанных компонентов путем создания каждой вершины вотобразить член своего собственного компонента (или набора).
Вы должны просто инициализировать каждую вершину (элемент) как репрезентативный элемент нового набора, вы можете сделать это, установив их в качестве родителя:
function MakeSet(x)
x.parent := x
2- Реализация Найти метод:
Найти репрезентативный элемент множества, который содержит вершину x:
function Find(x)
if x.parent == x
return x
else
return Find(x.parent)
The if Часть проверяет, является ли элемент представительным элементом или нет.мы устанавливаем все репрезентативные элементы наборов в качестве их первого элемента, устанавливая их как своих родителей.
3- И, наконец, когда вы получили все предыдущие вещи, простая часть реализует Union метод:
function Union(x, y)
xRoot := Find(x) // find representative element of first element(set)
yRoot := Find(y) // find representative element of second element(set)
xRoot.parent := yRoot // set representative element of first set
// as same as representative element of second set
Теперь, как вы должны запустить Kruskall?
Сначала поместите все узлы в n непересекающихся множеств с помощью метода MakeSet .На каждом шаге после нахождения нужного ребра (не отмеченного и минимального) найдите связанные наборы его вершин конечной точки методом Find (их репрезентативные элементы), если они одинаковые, отбросьте это ребро, потому что это ребро вызываетцикл, но если они находятся в разных наборах, используйте метод Union для объединения этих наборов.Поскольку каждый набор является деревом, объединение их является деревом.
Вы можете оптимизировать это, выбрав лучшую структуру данных для непересекающихся наборов, но пока я думаю, что этого достаточно.Если вас интересуют более сложные структуры данных, вы можете реализовать базовый способ rank , вы найдете его в вики. Это легко, но я не упомянул об этом, чтобы избежать недоумения.