보르 ů프카의 알고리즘

Borůvka's algorithm
보르 ů프카의 알고리즘
보르 ů프카의 알고리즘 애니메이션
학급최소 신장 트리 알고리즘
자료구조그래프
최악의 경우 성능

Bor ů프카의 알고리즘은 그래프에서 최소 스패닝 트리를 찾기 위한 그리디 알고리즘 또는 연결되지 않은 그래프의 경우 최소 스패닝 포리스트를 찾는 알고리즘입니다.

1926년 Otakar Bor ů프카가 모라비아의 효율적인 전력망을 구축하는 방법으로 처음 발표했습니다. 이 알고리즘은 1938년 초케에 의해 재발견되었고,[4] 1951년 플로렉, 우카시에비치, 퍼칼, 스타인하우스, 주브르지키에 의해 [5]재발견되었으며, 1965년 조르주 솔린에 의해 재발견되었습니다.[6] 특히 병렬 컴퓨팅 문헌에서는 이 알고리즘을 흔히 솔린의 알고리즘이라고 부릅니다.

알고리즘은 그래프의 각 정점에 결합된 최소 가중치 에지를 찾고 해당 에지를 모두 포리스트에 추가하는 것으로 시작됩니다. 그런 다음 지금까지 구축된 각 나무에서 다른 나무로 최소 무게의 가장자리를 찾아 그 모든 가장자리를 숲에 추가하는 비슷한 과정을 반복합니다. 이 프로세스를 반복할 때마다 그래프의 각 연결된 구성 요소 내의 트리 수가 이전 값의 최대 절반으로 줄어들기 때문에 대수적으로 여러 번 반복하면 프로세스가 완료됩니다. 그러면 추가한 에지 집합이 최소 스패닝 포리스트를 형성합니다.

의사코드

다음은 Bor ů프카 알고리즘의 기본적인 구현을 보여주는 의사 코드입니다. 조건부 절에서는 모든 모서리 UV가 "없음"보다 더 저렴한 것으로 간주됩니다. 완성된 변수의 목적은 포리스트 F가 아직 스패닝 포리스트인지 여부를 확인하는 것입니다.

에지에 뚜렷한 가중치가 없는 경우, 예를 들어 정점 또는 에지의 전체 순서에 따라 일관된 타이 브레이킹 규칙을 사용해야 합니다. 이는 정점을 정수로 표현하고 직접 비교, 메모리 주소 비교 등을 통해 달성할 수 있습니다. 생성된 그래프가 실제로 포리스트(forest), 즉 사이클을 포함하지 않도록 하려면 타이 브레이킹 규칙이 필요합니다. 예를 들어, 노드 {a,b,c}와 모든 간선이 가중치 1인 삼각형 그래프를 생각해 보자. 그런 다음 {a}의 경우 ab, {b}의 경우 bc, {c}의 경우 ca를 최소 가중치 에지로 선택하면 주기가 생성될 수 있습니다. 에지를 먼저 소스별로 정렬한 후 대상별로 정렬하는 타이 브레이킹 규칙으로 인해 주기가 생성되지 않아 최소 스패닝 트리 {ab,bc}가 생성됩니다. 

알고리즘 Bor ůvka 입력: 가중치가 부여된 무방향 그래프 G = (V, E). 출력: F, G의 최소 신장 포리스트.      포리스트 F를 (V, E')로 초기화합니다(여기서 E' = {}).      완료:= 아직 완료되지 않은 상태에서 false F의 연결된 성분을 찾아 각 정점에 해당 성분을 할당합니다. 각 성분의 가장 저렴한 간선을 E의 각 간선 uv에 대해 "없음"으로 초기화합니다. 여기서 u와 v는 F의 다른 성분에 있는 경우: wx가 u의 성분의 가장 저렴한 간선이라고 가정합니다. is-referred-over(uv, wx) 그런 다음 utyz 성분에 대해 가장 저렴한 에지로 uv를 설정합니다 vis-referred-over(uv, uv) 성분에 대해 가장 저렴한 에지입니다. yz) 그런 다음 모든 구성 요소의 가장 저렴한 에지가 "없음"으로 설정된 경우 uv를 v의 구성 요소의 가장 저렴한 에지로 설정하고 // 더 이상 트리를 병합할 수 없습니다. 완료되었습니다:= true other complete:= false 가장 저렴한 에지가 "없음"이 아닌 각 구성 요소의 가장 저렴한 에지를 E' 함수에 추가합니다. is- preferred-over(edge1, edge2)는 반환(edge2는 "없음") 또는 (weight(edge1) < weight(edge2)) 또는 (weight(edge1) = weight(edge2) 및 tie-breaking-rule(edge1, edge2) 함수 tie-breaking-rule(edge1, edge2)은 tie-breaking 규칙이며, tie의 경우 edge1이 edge2보다 선호되는 경우에만 true를 반환합니다.

최적화를 위해 동일한 구성 요소의 두 정점을 연결하는 것으로 확인된 각 에지를 G에서 제거할 수 있으므로 이후 구성 요소에서 가장 저렴한 에지를 검색하는 시간에 기여하지 않습니다.

복잡성

Bor ůvka의 알고리즘은 외부 루프가 종료될 때까지 O(log V) 반복을 수행하고, 따라서 시간 O(E log V)에 실행된다는 것을 보여줄 수 있습니다. 여기서 E는 간선의 수이고, V는 G의 정점의 수입니다(E ≥ V 가정). 평면 그래프에서, 그리고 더 일반적으로 그래프 사소한 작업으로 닫힌 그래프 계열에서, 알고리즘의 각 단계 후에 각 구성 요소 쌍 사이의 가장 저렴한 에지를 제외하고 모두 제거함으로써 선형 시간 내에 실행되도록 만들 수 있습니다.[7]

예

이미지 구성 요소들 묘사
{A}
{B}
{C}
{D}
{E}
{F}
{G} 		이것은 저희의 원래 가중치 그래프입니다. 가장자리 근처의 숫자는 무게를 나타냅니다. 처음에는 모든 정점 자체가 성분(파란색 원)입니다.
{A,B,D,F}
{C,E,G} 		외부 루프의 첫 번째 반복에서는 모든 구성 요소 중 최소 무게 에지가 추가됩니다. 일부 모서리는 두 번(AD, CE) 선택됩니다. 두 가지 구성품이 남아 있습니다.
{A,B,C,D,E,F,G} 두 번째 및 마지막 반복에서 나머지 두 구성요소 각각의 최소 무게 에지가 추가됩니다. 이들은 우연히 같은 에지입니다. 하나의 구성 요소가 남아 있고 우리는 끝입니다. 두 끝점이 동일한 성분에 있으므로 에지 BD가 고려되지 않습니다.

기타 알고리즘

이 문제에 대한 다른 알고리즘으로는 Prim의 알고리즘과 Kruskal의 알고리즘이 있습니다. Prim의 알고리즘과 Bor ů프카의 알고리즘을 결합하면 빠른 병렬 알고리즘을 얻을 수 있습니다.

Karger, Klein 및 Tarjan으로 인해 Bor ů프카의 알고리즘을 부분적으로 기반으로 한 더 빠른 무작위 최소 신장 트리 알고리즘이 예상 O(E) 시간에 실행됩니다. Bernard Chazelle에 의해 가장 잘 알려진 (결정론적) 최소 신장 트리 알고리즘 또한 부분적으로 Bor ů프카를 기반으로 하며 O(E α(E,V) 시간에서 실행되며, 여기서 α는 역 아커만 함수입니다. 이러한 무작위 및 결정론적 알고리즘은 Bor ů프카 알고리즘의 단계를 결합하여 연결해야 할 구성 요소의 수를 줄이고 구성 요소 쌍 간의 에지 수를 줄이는 다른 유형의 단계와 결합합니다.

메모들

  1. ^ Borůvka, Otakar (1926). "O jistém problému minimálním" [About a certain minimal problem]. Práce Mor. Přírodověd. Spol. V Brně III (in Czech and German). 3: 37–58.
  2. ^ Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)". Elektronický Obzor (in Czech). 15: 153–154.
  3. ^ Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001). "Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history". Discrete Mathematics. 233 (1–3): 3–36. doi:10.1016/S0012-365X(00)00224-7. hdl:10338.dmlcz/500413. MR 1825599.
  4. ^ Choquet, Gustave (1938). "Étude de certains réseaux de routes". Comptes Rendus de l'Académie des Sciences (in French). 206: 310–313.
  5. ^ Florek, K.; Łukaszewicz, J.; Perkal, J.; Steinhaus, Hugo; Zubrzycki, S. (1951). "Sur la liaison et la division des points d'un ensemble fini". Colloquium Mathematicum (in French). 2 (3–4): 282–285. doi:10.4064/cm-2-3-4-282-285. MR 0048832.
  6. ^ Sollin, Georges (1965). "Le tracé de canalisation". Programming, Games, and Transportation Networks (in French).
  7. ^ Eppstein, David (1999). "Spanning trees and spanners". In Sack, J.-R.; Urrutia, J. (eds.). Handbook of Computational Geometry. Elsevier. pp. 425–461.; Mareš, Martin (2004). "Two linear time algorithms for MST on minor closed graph classes" (PDF). Archivum Mathematicum. 40 (3): 315–320..
  8. ^ Bader, David A.; Cong, Guojing (2006). "Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs". Journal of Parallel and Distributed Computing. 66 (11): 1366–1378. CiteSeerX 10.1.1.129.8991. doi:10.1016/j.jpdc.2006.06.001. S2CID 2004627.
  9. ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM. 42 (2): 321–328. CiteSeerX 10.1.1.39.9012. doi:10.1145/201019.201022. S2CID 832583.
  10. ^ Chazelle, Bernard (2000). "A minimum spanning tree algorithm with inverse-Ackermann type complexity" (PDF). J. ACM. 47 (6): 1028–1047. CiteSeerX 10.1.1.115.2318. doi:10.1145/355541.355562. S2CID 6276962.