최소 스패닝 트리를 위한 병렬 알고리즘

그래프 이론에서 V ${\displaystyle =}$ {$displaystyle$ V $= n$ } $및$ ${\displaystyle E}$ ${\displaystyle =}$ {$displaystyle$ E $= m$}인 그래프 G $=$ ($V,$ E$)$의 최소 스패닝 트리(MST)$T{\displaystyle }$ {$displaystyle$ T$}$는 모든 정점을 포함하는 그래프 G$${\$style$ G$}$의 트리 하위 그래프입니다.

MST는 실용적이고 이론적인 다양한 분야에서 유용하고 다용도적인 도구입니다.예를 들어, 한 창고에서 특정 제품을 여러 상점에 공급하려는 회사는 창고에서 시작되는 MST를 사용하여 각 회사 상점으로 가는 최단 경로를 계산할 수 있습니다.이 경우 상점과 창고는 정점으로 표시되고 이들 사이의 도로 연결은 모서리로 표시됩니다.각 모서리에는 해당 도로 연결의 길이가 라벨로 표시됩니다.

G$(\displaystyle$ G$)$가 엣지 언웨이트인 $경우{\displaystyle }$ 모든 스패닝트리는 엣지 수가 같기 때문에 무게가 동일합니다.엣지 무게 부여의 경우$G의 모든$ 스패닝트리 중 가장 낮은 엣지의 무게 합계를 최소 스패닝트리(MST$)$라고 부릅니다그것은 반드시 독특한 것은 아니다.보다 일반적으로, 반드시 접속되어 있지 않은 그래프에는 최소 스패닝 포레스트가 있습니다.이 포레스트는 연결된 각 컴포넌트의 MST 조합으로 구성됩니다.

MST를 찾는 것은 그래프 이론에서 광범위한 문제이기 때문에, 그것을 해결하기 위한 많은 순차적 알고리즘이 존재한다.그 중에는 각각 MST의 다른 특성을 이용하는 Prim 알고리즘, Kruskal 알고리즘 및 Bor'vka 알고리즘이 있다.모두 유사한 방식으로 작동합니다. E$(\displaystyle$ E$)$의 하위 집합은 유효한 MST가 발견될 때까지 반복적으로 성장합니다.그러나 실제적인 문제는 매우 큰 경우가 많기 때문에(때로는 도로 네트워크의 가장자리가 수십억 개에 달할 수 있음), 퍼포먼스가 중요한 요소입니다.이를 개선하는 방법 중 하나는 기존의 MST 알고리즘을 ^[1]병렬화하는 것입니다.

프림 알고리즘

이 알고리즘은 MST의 컷 속성을 사용합니다.다음으로 간단한 고급 의사 코드의 실장을 나타냅니다.

${\displaystyle T}$ ${\displaystyle \leftarrow }$ { $displaystyle{\displaystyle }$ T \ $gets$ \$$$emptyset$} $S$${\displaystyle }$ ${\displaystyle \leftarrow }$ { $s }$ { $displaystyle$$$s$$$$${\displaystyle \}}$$$${\displaystyle 。}$ $여기$서 $s$ { $displaystyle$$$V - $1$$}회$ ${\displaystyle 반복}$하여 가장 밝은$(u$${\displaystyle }$, $v )$를 찾습니다.${\displaystyle (}$ ( $V$) $、$ { $displaystyle$v \ $in$( $V$${\displaystyle }$ \ $setminus$S ) ${\displaystyle S}$ ${\displaystyle \leftarrow }$ S ${\displaystyle v}${ $v$} { $displaystyle$$S\gets S\cup$\ { $v$${\displaystyle }$ \ { v \ ${\displaystyle \}}$ ${\displaystyle T}$ ${\displaystyle \leftarrow }$ ${\displaystyle T}$(${\displaystyle }${ ( $u$,$$v$$ ) { } { displaystyle $T\gets$ t \ cup \ { \ {$}$ rets } $반환$

각 모서리는 정확히 두 번, 즉 각 끝점을 검사할 때 관찰됩니다.각 정점은 각 루프 반복에서 가장 가벼운 에지를 선택하는 것을 제외하고 총 O${\displaystyle }$(${\displaystyle n}$ +${\displaystyle m}$) \ $displaystyle$O ($n$ + $m$)$연산$에 대해 정확히 한 번 검사됩니다.이 선택은 priority queue(PQ; 우선 큐)를 사용하여 실행되는 경우가 많습니다.각 엣지별로 최대 1개의 ${\displaystyle \mathrm{decrementKey}}$ 조작($O{\displaystyle }$( 1${\displaystyle }$)$${ $displaystyle$O (1$)$ )이 실행되고 각 루프 반복은 1개의 deleteMin 조작(${\displaystyle }$( ${\displaystyle \log n}$n )$$\ $displaystyle$ O ( \ $log$ n )$$}$$ )를 실행합니다.따라서 Fibonacci 힙을 사용하면 Prim 알고리즘의 총 런타임은 점근적으로 O${\displaystyle (m}$ ${\displaystyle +}$ ${\displaystyle n}$ ${\displaystyle \log n}$n $)\displaystyle$ O$(m+n\log$ n$)\}$가 $됩니다{\displaystyle }$.

루프는 본질적으로 순차적이며 적절히 병렬화할 수 없다는 점에 유의해야 합니다.이는 S$${\$displaystyle$ S$}$ 및$$ V$display$ S {\$displaystyle$V$\setminus$ S$}$의 한쪽 끝점이 있는 가장 밝은 가장자리가$$T {\$displaystyle$$$T$\}$에 추가됨에 따라 변경될 수 있으므로 가장 밝은 가장자리 두 개를 동시에 선택할 수 없습니다.그러나 병렬화에 대한 몇 가지 시도가 존재합니다.

1가지 방법은 O${\displaystyle }$(${\displaystyle n}$){ $displaystyle$O ($n$ )프로세서를$$ $사용$하여 EREW-PRAM ^[2]머신의${\displaystyle }$O ( $){$ $displaystyle$O (1$)$에서의 PQ 액세스를 지원함으로써 총 실행시간을${\displaystyle }O{\displaystyle }$ (${\displaystyle n}$ +${\displaystyle m}$){ $displaystyle$O ($n$ + $m$ displaystyle O ( n + m )

크루스칼 알고리즘

Kruskal의 MST 알고리즘은 MST의 사이클 속성을 사용합니다.다음에, 고도의 의사 코드의 표현을 나타냅니다.

${\displaystyle T}$ ${\displaystyle \leftarrow }$ ({$displaystyle$ T$\$$gets$$$$}$ 포레스트는 각각의 서브트리$,$ v$)$에 있는 모든 정점을 무게 오름차순으로 나타냅니다$.$ $({$$displaystyle$$u$${\displaystyle \}}$ 및$$ $v{\displaystyle }${{$displaystyle$ v${\displaystyle \}}$는 T $displaystyle$ T$}$의 $서로{\displaystyle }$ 다른 서브트리에 있는 $경우{\displaystyle }$${\displaystyle ).}$}} 반환$$$$T

$T$$(\$displaystyle T)의 서브트리는 union-find 데이터 구조에 저장되므로 $상각후{\displaystyle }$ O${\displaystyle (\alpha }$ ${\displaystyle (}$m$)\displaystyle$ O$(\alpha$(${\displaystyle m,}$$$$))\displaystyle \alpha$($m$, n${\displaystyle )\backslash }$$displaystyle$ \alpha (m, $n)}$에서 $두$ 정점이 동일한 서브트리에 있는지 확인할 수 있습니다${\displaystyle .}$따라서 알고리즘의 총 실행시간은 $O{\displaystyle }$( ${\displaystyle s}$ ${\displaystyle o}$ r${\displaystyle }$t (${\displaystyle n}$) +${\displaystyle }$α (${\displaystyle n}$)$${ $displaystyle$O ( $sort$( n ) + \$alpha$ ($n$ )$$} 。$여기$서${\displaystyle }$α ( n )는 단일값의 역Ackerman 함수를 나타냅니다.여기서${\displaystyle \alpha }$ ( n ) \ $displaystyle \ alpha$ ($n$ )는$$ 5 미만의 정수를 생성합니다.

접근법 1: 정렬 단계 병렬화

프림의 알고리즘과 유사하게, Kruskal의 접근법에는 고전적인 변형에서는 병렬화할 수 없는 구성요소가 있다.예를 들어, 두 개의 정점이 동일한 하위 트리에 있는지 여부를 판단하는 것은 두 개의 결합 연산이 동시에 동일한 하위 트리에 결합하려고 시도할 수 있기 때문에 병렬화하기가 어렵습니다.병렬화를 위한 유일한 기회는 분류 단계에 있습니다.O${\displaystyle }$( ${\displaystyle \log n}$n$$) { $displaystyle$ O ( \ $log$n ) }프로세서에서는$$ $최적$의 경우 정렬이 선형적이기 때문에 총 런타임은${\displaystyle O}$ ( ${\displaystyle m\alpha }$( n${\displaystyle }$) { $displaystyle O$( $m$\ $alpha$( n )$$} 로 $줄일{\displaystyle }$ 수 있습니다.

접근법 2: 필터-크루스칼

또 다른 접근법은$T를$보다$$ 적극적으로 $성장$시켜 원래의 알고리즘을 수정하는 것입니다.이 아이디어는 Osipov ^[3][4]등에 의해 제시되었다.Filter-Kruskal의 기본 개념은 정렬 비용을 절감하기 위해 가장자리를 빠른 정렬 및 필터링하는 것과 유사한 방법으로 분할하는 것입니다.다음에, 고도의 의사 코드의 표현을 나타냅니다.

filterKruskal ($$ \ $displaystyle$G $$) :m< \ $displaystyle$ m< } Kruskal인 문턱 값:반환 kruskal(G{\displaystyle G})중심)chooseRandom(E{\displaystyle E})(E≤{\displaystyle(E_{\leq}}, E>)←{\displaystyle E_{>})\gets}한 ←{A\gets\displaystyle}filterKruskal(E≤{\displaystyle E_{\leq}})partition(E{\displaystyle E}, 피벗).   e  $←$ {\$displaystyle E_{>}\gets }$ ${\displaystyle \mathrm{필터<img\; alt="\{\backslash displaystyle\; E\_\{>\}\backslash gets\; \}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/eef129a24eefa05529d77540a9dc2ae8cae8c183"\; style="vertical-align:\; -0.671ex;\; width:6.195ex;\; height:2.509ex;">}}$ E  ${\$ A ${\displaystyle \leftarrow }$ {\$displaystyle$$A$$\$$gets$A}$$$∪$ {\displaystyle $E_$ filterKruskal$$$($$$$>$ {\$displaystyle$ E_$${})을 $반환$합니다$.$E≤ ←∅{\displaystyle E_{\leq}\gets \emptyset}E>← ∅{\displaystyle E_{>}\gets}foreach(u, v)∈ E{\displaystyle(u,v)\in E}:weight(u, v{\displaystyle u,v})≤{\displaystyle \leq}피벗:E≤← E≤ ∪(u, v){\displaystyle E_{\leq}\gets E_ \emptyset.{\leq}\cup{(u,v)}}일 경우 다른 E>← E>∪(u, v)}반환(E≤{\displaystyle E_{\leq}}, E>,{\displaystyle E_{>}})filter(E{\displaystyle E}):Efil tered← ∅{\displaystyle E_{필터링 된}\gets \emptyset}foreach(u, E_{>}\cup{(u,v)}{\displaystyle E_{>}\gets.v=∈ E{\displ$aystyle (u,v)\$$in$ E$\}$ : find-set(u)$\ne {\displaystyle }$ \ $displaystyle$\$neq }$ find-set$$ (${\displaystyle v}$): ${\displaystyle E_{}}$ ${\displaystyle {\mathrm{fi}}_{}}$ ${\displaystyle t_{}}$ ${\displaystyle e_{}}$ ${\displaystyle r_{}}$ ${\displaystyle e_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle E_{}}$ ${\displaystyle {\mathrm{fi}}_{}}$ ${\displaystyle t_{}}$ ${\displaystyle e_{}}$ r e ${\displaystyle d_{}{}_{}}$ (${\displaystyle u}$, v$$) \ $displaystyle E_${ $filtered$}\ $gets$ E_{ filtered } $furnaltered{\displaystyle {}_{}}$ （$$） ${\displaystyle {\mathrm{e<img\; alt="\{\backslash displaystyle\; E\_\{filtered\}\backslash gets\; E\_\{filtered\}\backslash cup\; \{(u,v)\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/6b1d1e84c9280c884b7aa6f1b1749ae4f2be4a23"\; style="vertical-align:\; -1.005ex;\; width:26.77ex;\; height:3.009ex;">}}_{}}$ e e e e e e e e e e e e e e e e e e e e e e e 。

정렬, 분할 및 필터링은 가장자리가 코어 간에 단순히 분할되는 직관적으로 쉬운 병렬화를 가지므로 필터-크루스칼이 병렬화에 더 적합합니다.

보르시브카 알고리즘

Borvvka 알고리즘의 배후에 있는 주된 아이디어는 가장자리 수축이다.엣지${\displaystyle }${${\displaystyle u,}$ ${\displaystyle v}$$$$}{$$displaystyle$$\{u,v\}}$을(를$$) 그래프에서 $삭제$한 후 모든${\displaystyle }$엣지 {${\displaystyle w,v\}e}$E {\$displaystyle$\{$w$$,v\}\in$ E${\displaystyle }$}를 {$,$u$displaystyle \{w,u$로 리다이렉트하여 엣지 {u}를 축소합니다.이러한 새 모서리에는 이전 모서리의 무게가 유지됩니다.MST의 무게뿐만 아니라 MST가 어떤 가장자리를 구성하는지를 결정하는 것이 목적이라면 가장자리를 수축시킨 정점 쌍 간에 주목해야 한다.다음으로 높은 수준의 의사 코드의 표현을 제시하겠습니다.

반면 V<T;0S{\displaystyle V>0}v에 ∅{\displaystyle S\gets \emptyset}←∅{\displaystyle T\gets \emptyset}←∈ V{v\in V\displaystyle}S← S{\displaystyle S\gets S}∪{\displaystyle \cup}{u, v}∈ E{\displaystyle\와 같이{u,v\}\in E}에{u, v}∈ S{년.displa$ystyle \{u,v\}\in$S 계약$$${\displaystyle }${$}$ {$displaystyle$\{$u,v\}$ $T$${\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle T}$ ${\displaystyle \cup }$ ${\displaystyle S}$ \$displaystyle$ T$\gets$T\$cup$ S$$} 반환$$ T

수축으로 인해 한 쌍의 정점 사이에 여러 모서리가 생길 수 있습니다.O${\displaystyle }$(${\displaystyle m}$ ) \ $displaystyle$O ($m$ )$$에서는 가장 가벼운 것을 직관적으로 선택할 수 없습니다.다만, 정점을 공유하는 모든 수축이 병렬로 행해진다면, 이것은 가능합니다.정점이 1개밖에 남지 않은 경우 재귀는 정지합니다.즉, 알고리즘에서는 ${\displaystyle \mathrm{로그}}$의 ${\displaystyle \mathrm{최대}}$n개$(\displaystyle$ \$log$ n$)$의 반복이 필요하기 때문에 O$m$ log$n$n$)$의 합계 실행 시간이 됩니다.

병렬화

이 algorithm[5][6][7]의 하나의 가능한 parallelisation고 T∈ O(로그 c⁡ m){T(m,n,p)\in O(\log ^{c}m)\displaystyle}(m, n, p)지속적인 c{\displaystyle c}. 그는 존재하는polylogarithmic 시간 복잡도, 즉 T⋅ p(m, n, p)∈ O(m로그 ⁡ n){\displaystyle T(m,n,p)\cdot p\in O(nm\log)}를 산출한다.T이 전무하다는 $($ ${\displaystyle m}$,${\displaystyle n}$ ,${\displaystyle p}$) { $displaystyle$$$T ($m$ ,$n$ , $p$} { $displaystyle$ p$$}프로세서를$$$$ $탑재$한 머신 상에서 m$${ $displaystyle$ m$}$개의$$ 엣지,$n{\displaystyle }$ { $displaystyle$ n$}$개의$$ 정점을 $가진{\displaystyle }$ 그래프의 실행시간을 나타냅니다.기본 개념은 다음과 같습니다.

반면 V1{\displaystyle V1} 가벼운 사건 O// edges을 찾(mp+로그 ⁡ n+로그 ⁡ p)각 꼭지점에 // O(np+로그⁡ n){O({\frac{n}{p}}+\log n)\displaystyle}계약 O// 각 부분 그래프(해당 부분 그래프를 할당{O({\frac{m}{p}}+\log n+\log p)\displaystyle}.  mp  $displaystyle$

그러면 MST는 발견된 가장 가벼운 모든 가장자리로 구성됩니다.

이 병렬화에서는 G ${\displaystyle =}$ ( ${\displaystyle V}$,${\displaystyle E}$) \ $displaystyle$ G= ($V$ , $E$의 $인접{\displaystyle }$ 배열 그래프가 사용됩니다.이 그래프는 3개의 배열로 구성됩니다.$길이{\displaystyle }$ n의${\displaystyle }$$δ$ \ $displaystyle$ \ Gamma$$} + ${\displaystyle \mathrm{길이}}$1의 δ \ $displaystyle n$$+$1의$$$$ 각$$m $displaystyle$$$엔드포인트 $m$의$$m$$ $m{\displaystyle }$ of of of $of$ of of of of of of of of of of of of of of of of of of m of of of of of of m of$$ of of of of of of of of of of of of of of m$m{\displaystyle }$$($$displaystyle$ m$)$ $가장자리$ 및 c$(displaystyle$ c$)$ 길이 $m{\displaystyle }$$($$displaystyle$ m$)$의 모서리 중량을 나타냅니다.$i에$$$입사하는 각$$$엣지$의 다른 한쪽 끝은 ${\displaystyle 【【【【【i}$- $】【displaystyle】【i-1】】【【【$$I$】】【【I】【$Displaystyle】$의 엔트리에서 찾을 수 있습니다.】【${\displaystyle \mathrm{I}】\{}$$displaystyle$ \gamma $[i$$]$Γ{\displaystyle \Gamma}에서 i{\displaystyle 나는}-th 가장자리의 무게 c[나는]{\displaystyle c[나는]}에 iγ{\displaystyle \gamma}에 사이 vertices 너{\displaystyle u}그리고 v{\displaystyle v}만일Γ[u]≤ 나는 <-th 가장자리{\displaystyle 나는}, Γ는 경우에는 u+ 찾을 수 있다.1$[\displaystyle \Gamma [u]\leq$ i <\$Gamma [u+1]$ 및 ${\displaystyle [}$ [ ${\displaystyle i}$]$=$ ${\displaystyle v}$\ $displaystyle \ display$ style [ i ]= $v$

가장 가벼운 사고 에지 찾기

먼저 엣지는 각 $\displaystyle$p 프로세서$$ 간에 분산됩니다.i$(\displaystyle$$$i$)$ -th$$ $프로세서$는${\displaystyle \frac{i}{}}$ [ i ${\displaystyle \frac{}{}}$ p$](\displaystyle$ \$gamma$[ { \$$$frac$ { $im$} { p$$} })와 ${\displaystyle [\frac{}{}}$[ (${\displaystyle \frac{i}{}}$ +${\displaystyle \frac{1}{}}$) m${\displaystyle \frac{}{}}$ -${\displaystyle 1}$](\ $displaystyle$\$gamma$ [ ${$ $( i$ +$1$) $m$} {$p}-1$ 사이에 저장된 엣지를 수신합니다.또한 각 프로세서의 엣지가 필요합니다.$$}은$($는) 엣지의 엔드포인트 중 하나만을 저장하고 ${\displaystyle 이}$를 $pr$ d ${\displaystyle$pred}에 저장합니다. 이 정보는 $p${\$displaystyle$ p$$} 바이너리 검색을 $사용$하는$$${\displaystyle O\frac{}{}(\frac{\log }{}}$${\displaystyle n}$n${\displaystyle )}$ \$displaystyle$O(\$log$$$n) \$displaystyle$ O$(\$ +$$p$)에서$$$얻을$$수 $있습니다$.실제로 후자의 접근법이 점근적으로 더 나쁠지라도 때로는 더 빠르다.

이제 각 프로세서가 각 정점에 입사하는 가장 가벼운 엣지를 결정합니다.

V나는 치고 p;{\frac{(i+1)m}{p}}-1;ve++}만약Γ[v+1])e{\displaystyle \Gamma[v+1]=e}++{\displaysty e←에{\displaystyle v\gets}find(나는 치고 p{\displaystyle{\frac{나는}{p}}},Γ{\displaystyle \Gamma})e<>(나는 1+)mp− 1;e++{\displaystyle e\gets{\frac{나는}{p}};e< ←.르 v++} [   [   [ $v$]{ $displaystyle c$ [ ${\displaystyle }$$]<$ c [ $v$]}${\displaystyle p}$ ${\displaystyle rd}$[ v $]←$ e \ $displaystyle pred$ [$v$ ]\$gets$ e$$인 경우$$

여기에서는, 몇개의 정점이 복수의 프로세서에 의해서 처리되는 문제가 발생합니다.이에 대한 가능한 해결책은 각 프로세서가 $독자적$인 ${\displaystyle \mathrm{pr}}$ ${\displaystyle e}$ v$$\ $display style$prev \ display style prev \ array를$$ 가지고 있으며, 나중에 리덕션을 사용하는 다른 프로세서와 조합됩니다.각 프로세서는 최대 2개의 정점을 가지며, 다른 프로세서에 의해 처리되며 각 감소폭은${\displaystyle O}$(${\displaystyle \log )}$ p$)\display style$O(\$log$p$)\}$입니다.${\displaystyle 따라서\frac{}{}}$ 이 순서의 총 실행시간은 O${\displaystyle }$( m${\displaystyle p}$ + log${\displaystyle }$"${\displaystyle n}$ + ${\displaystyle \log }$"${\displaystyle p}$) { $displaystyle$ O ( { \ $frac${$m$} { $p}$ ) + \ $log$ n + \ $log$ p$\}$ 입니다.

정점에 하위 그래프 할당

이전 단계에서 수집한 모서리만으로 구성된 그래프를 관찰합니다.이러한 모서리는 가장 가벼운 입사 모서리인 정점에서 멀리 떨어져 있습니다.결과 그래프는 약하게 연결된 여러 구성요소로 분해됩니다.이 단계의 목적은 부품이 되는 구성요소를 각 정점에 할당하는 것입니다.모든 정점은 정확히 하나의 나가는 에지를 가지므로 각 컴포넌트는 유사 트리입니다. 즉, 컴포넌트의 가장 가벼운 에지와 반대 방향으로 병렬로 실행되는 단일 추가 에지가 있는 트리입니다.다음 코드는 이 추가 에지를 루프로 변환합니다.

모두 병렬 ${\displaystyle v\in V}$      ${\displaystyle w\gets pread[v]}$     한다면 ${\displaystyle pred[w]=v\land v<w}$          ${\displaystyle pred[v]\gets v}$ 

약하게 연결된 모든 구성 요소는 루트에 루프가 있는 방향 트리가 됩니다.이 루트는 각 컴포넌트의 대표로서 선택됩니다.다음 코드에서는 각 정점에 대표성을 할당하기 위해 배율을 사용합니다.

하는 동안에 $\displaystyle \exists v:pred[v]\neq pred[v]}$     모든 것 ${\displaystyle v\in V}$          ${\displaystyle pred[v]\gets pred[v]}$ 

이제 모든 서브그래프는 별입니다.일부 고급 기술을 사용하는 경우 이 단계에서는 O${\displaystyle (n}$p + log${\displaystyle n}$n )$${ $displaystyle$ O$({\frac {n}$ {$p}}+\log$ n$)}$ 시간이$$ $필요$합니다.

서브그래프 축소

이 단계에서는 각 하위 그래프가 하나의 정점으로 축소됩니다.

${\displaystyle k}$ $←$ {\$displaystyle$ k$\$$gets$ $}$개수의$$ $서브그래프{\displaystyle {}^{}}$ V$$ ${\displaystyle \leftarrow }$ {${\displaystyle 0}$, ${\displaystyle ...}$ ,${\displaystyle k}$ - $}{$ ${\displaystyle 0}$ , \ $displaystyle$ V \ gets $\${ 0 , \ $displaystyle f$: }${\displaystyle 스타}$$$${\displaystyle {}^{}}$ $루트{\displaystyle }$${\displaystyle }\to {\displaystyle }$ {${\displaystyle 0}$, ${\displaystyle ...}$, ${\displaystyle \mathrm{k}}$ - 1$$} \ $displaystyle$ \ $arrow \$ 0 , 1 } \ 1$$、 k - $1$。${\$$$$}}$

${\displaystyle O\frac{}{}}$( n${\displaystyle \frac{p}{}}$ + ${\displaystyle \log p}$p$$) { $displaystyle$ O ( { \ $frac${ $n$} { $p$} + \ $log$ p$$} ) 에서는 프리픽스 합계를 사용하여 bijectionive 함수를 찾을 수 있습니다.새로운 정점과 엣지 세트가 생겼기 때문에 인접 배열을 재구축해야 합니다.이는 O${\displaystyle (\frac{m}{}}$p + ${\displaystyle \log }$ ${\displaystyle p}$ $)(\displaystyle$ O$({\frac {m}{p}+log$ p$)})$의 E $"\$ E$"$에서 $수행$할 수 있습니다.

복잡성

Each iteration now needs ${\displaystyle O({\frac {m}{p}}+\log n)}$ time and just like in the sequential case there are ${\displaystyle \log n}$ iterations, resulting in a total runtime of ${\displaystyle O(\log n({\frac {m}{p}}+\log n))}$. If ${\displaystyle m\in \mathrm{\Omega }(p{\log }^{}}$${\displaystyle 2^{}\mathrm{\mu p}}$( \ $displaystyle$m \ $in \$Omega ( p \ $log$^ {$2 p$)알고리즘의$$ 효율은${\displaystyle }\delta$ ( ${\displaystyle 1}$)\ $displaystyle$\$Theta (1)$$m{\displaystyle oO}$ (${\displaystyle }$n )$${ $displaystyle$m \ $in$O ($n$ ) m$$ 、 매우 효율적입니다.

기타 알고리즘

MST를 검출하는 문제를 다루는 다른 병렬 알고리즘이 여러 개 있습니다.이러한 프로세서 수를 선형으로 설정하면 O${\displaystyle }$( ${\displaystyle \log )}$ n $)\display style$ O$(\log$^[8][9]n$)}$에서 이를 실현할 수 있습니다.Bader와 Cong는 최적의 시퀀셜 ^[10]알고리즘보다8개의 코어로 5배 빠른 MST 알고리즘을 제시했습니다.

또 다른 과제는 외장 메모리 모델입니다. Dementiev 등에 의해 제안된 알고리즘이 내장^[11] 메모리만을 사용하는 알고리즘보다 2~5배 느리다고 주장되고 있습니다.

레퍼런스