algorithm
Алгоритм Крускаля
Поиск…
замечания
Алгоритм Крускала - это жадный алгоритм, используемый для поиска минимального связующего дерева (MST) графа. Минимальное остовное дерево - это дерево, которое соединяет все вершины графа и имеет минимальный общий вес края.
Алгоритм Крускаля делает это путем многократного выделения краев с минимальным весом (которые еще не находятся в MST) и добавляет их к окончательному результату, если две вершины, связанные этим ребром, еще не соединены в MST, в противном случае он пропускает это ребро. Union. Поиск структуры данных может использоваться для проверки того, что две вершины уже подключены в MST или нет. Несколько свойств MST заключаются в следующем:
- MST графа с
n
вершинами будет иметь ровноn-1
ребер. - Существует единственный путь от каждой вершины до любой другой вершины.
Простая, более подробная реализация
Чтобы эффективно обрабатывать обнаружение циклов, мы рассматриваем каждый узел как часть дерева. При добавлении ребра мы проверяем, являются ли его два компонентных узла частью различных деревьев. Первоначально каждый узел составляет одноузловое дерево.
algorithm kruskalMST'(G: a graph)
sort G's edges by their value
MST = a forest of trees, initially each tree is a node in the graph
for each edge e in G:
if the root of the tree that e.first belongs to is not the same
as the root of the tree that e.second belongs to:
connect one of the roots to the other, thus merging two trees
return MST, which now a single-tree forest
Простая реализация на основе несвязанного набора
Вышеупомянутая методология леса фактически представляет собой структуру данных, не связанных между собой, которая включает в себя три основные операции:
subalgo makeSet(v: a node):
v.parent = v <- make a new tree rooted at v
subalgo findSet(v: a node):
if v.parent == v:
return v
return findSet(v.parent)
subalgo unionSet(v, u: nodes):
vRoot = findSet(v)
uRoot = findSet(u)
uRoot.parent = vRoot
algorithm kruskalMST''(G: a graph):
sort G's edges by their value
for each node n in G:
makeSet(n)
for each edge e in G:
if findSet(e.first) != findSet(e.second):
unionSet(e.first, e.second)
Эта наивная реализация приводит к времени O(n log n)
для управления структурой данных с несвязанными наборами, приводящей к O(m*n log n)
времени для всего алгоритма Крускала.
Оптимальная реализация на основе непересекающихся множеств
Мы можем сделать две вещи, чтобы улучшить простые и субоптимальные неагрессивные суб-алгоритмы:
Эвристика сжатия
findSet
:findSet
не требует когда-либо обрабатывать дерево с высотой больше2
. Если он завершает итерацию такого дерева, он может связать нижние узлы напрямую с корнем, оптимизируя будущие обходы;subalgo findSet(v: a node): if v.parent != v v.parent = findSet(v.parent) return v.parent
Эвристическая слияния на основе высоты : для каждого узла сохраняйте высоту своего поддерева. При слиянии сделайте более высокое дерево родителем меньшего, тем самым не увеличивая рост человека.
subalgo unionSet(u, v: nodes): vRoot = findSet(v) uRoot = findSet(u) if vRoot == uRoot: return if vRoot.height < uRoot.height: vRoot.parent = uRoot else if vRoot.height > uRoot.height: uRoot.parent = vRoot else: uRoot.parent = vRoot uRoot.height = uRoot.height + 1
Это приводит к O(alpha(n))
времени для каждой операции, где alpha
является обратной для быстрорастущей функции Аккермана, поэтому она очень медленно растет и может быть рассмотрена O(1)
для практических целей.
Это делает весь алгоритм Крускала O(m log m + m) = O(m log m)
из-за начальной сортировки.
Заметка
Сжатие пути может уменьшить высоту дерева, поэтому сравнение высот деревьев во время операции объединения может не быть тривиальной задачей. Следовательно, чтобы избежать сложности хранения и вычисления высоты деревьев, результирующий родитель может быть выбран случайным образом:
subalgo unionSet(u, v: nodes):
vRoot = findSet(v)
uRoot = findSet(u)
if vRoot == uRoot:
return
if random() % 2 == 0:
vRoot.parent = uRoot
else:
uRoot.parent = vRoot
На практике этот рандомизированный алгоритм вместе с сжатием пути для операции findSet
приведет к сопоставимой производительности, но намного проще реализовать.
Простая реализация на высоком уровне
Сортируйте ребра по значению и добавьте каждый в MST в отсортированном порядке, если он не создает цикл.
algorithm kruskalMST(G: a graph)
sort G's edges by their value
MST = an empty graph
for each edge e in G:
if adding e to MST does not create a cycle:
add e to MST
return MST