algorithm
Kruskal의 알고리즘
수색…
비고
Kruskal 's Algorithm은 그래프의 MST (Minimum Spanning Tree) 를 찾는 데 사용되는 욕심 많은 알고리즘입니다. 최소 스패닝 트리는 그래프의 모든 정점을 연결하고 최소 전체 에지 가중치를 갖는 트리입니다.
Kruskal의 알고리즘은 반복적으로 최소 무게를 가진 에지를 골라내어 MST에 아직 연결되어 있지 않은 두 꼭지점이 MST에 아직 연결되어 있지 않으면 최종 결과에 추가합니다. 그렇지 않으면 가장자리를 건너 뜁니다. Union - 데이터 구조를 사용하여 두 꼭지점이 이미 MST에 연결되어 있는지 여부를 확인할 수 있습니다. MST의 몇 가지 속성은 다음과 같습니다.
-
n개의 정점이있는 그래프의 MST는 정확히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) 시간으로 이어져 Kruskal 알고리즘 전체에 대해 O(m*n log n) 시간을 유도합니다.
최적의 분리 된 집합 기반 구현
우리는 단순하고 차선이없는 분리형 서브 알고리즘을 개선하기 위해 두 가지를 할 수 있습니다 :
경로 압축 휴리스틱 :
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 는 빠르게 성장하는 Ackermann 함수의 역수이므로 매우 느리게 성장하며 실용적인 목적으로 O(1) 로 간주 될 수 있습니다.
초기 정렬 때문에 전체 Kruskal의 알고리즘 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 무작위 알고리즘은 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