最小生成樹的 Yao's 演算法

Borůvka 流派起初在 60 年代最為廣泛應用的地方在於平行計算。值得注意的是，1975 年 Yao（姚期智教授）從 Borůvka / Sollin 的論文和 Tarjan 的手稿中獲得了一些靈感，得到了一個關於最小生成樹的 \(O(m\log\log n)\) 時間的演算法。

找出 Borůvka 步驟中最可能浪費時間的地方

找出一個連通元件往外連的最小邊時，最原始的做法是逐一掃瞄與該連通元件相連的所有邊。這代表什麼意思呢？對於任何一條邊來說，如果它沒有被縮點縮掉，那麼它可能在每一個 Borůvka 步驟中都被看了一次。如果總共有 \(O(\log n)\) 個 Borůvka 步驟要做，那麼總花費的時間就是 \(O(m\log n)\)。

姚期智教授（以及 Tarjan）注意到，假若我們有一種方式可以預處理每個連通元件（或每個點）外連的邊，說不定能夠幫助我們省去很多麻煩。比方說，假設我們事先將每一個點往外連的邊全部都依照權重由小到大排列 \(e_1, e_2, \ldots\)，並使用一個標記 \(i_v\) 記得從這個點看出去我們目前考慮到的是哪條邊。這麼做有什麼好處呢？當我們要尋找一個連通元件 \(C\) 的外連邊的時候，我們可以從當前的標記 \(i_v\) 開始，把這個標記逐步增加，直到遇到一條「不往內連的邊」為止。而當 \(i_v\) 停下來的時候，這條邊 \(e_{i_v}\) 就會是從 \(C\) 往外連的許多邊之中權重最小邊的候選者之一。

如此一來，我們可以發現在同一輪 Borůvka 步驟被考慮到的邊，要嘛是候選者之一、要嘛就是因為已經是往內連的邊，再也不可能是未來的候選邊而被丟掉。因此，我們得到以下的引理。

引理 MST.9

如果所有點的相連邊都已經按照權重由小至大排好順序了，那麼找出最小生成樹只需要花費 \(O(m + n\log n)\) 的時間。

引理 MST.9 的證明

在每一個 Borůvka 步驟的當下，更新標記所需的時間為「因為 \(i_v\) 增加而被丟掉的邊」，加上「可能的候選邊」。每一條邊只會被丟掉兩次（因為有兩個端點）、而可能的候選邊顯然不超過總點數 \(n\)。因此，由引理 MST.7 可知花在考慮候選邊所需的總時間為 \(O(n\log n)\)、而花在前者更新標記的總時間為 \(O(m)\)；於是 MST.8 得證。

上述「預處理每個點外連邊」的方法，其實可以看成局部(local)版本的 Kruskal 演算法。為什麼呢？Kruskal 考慮的是把所有邊通通抓起來一起排序。而這邊我們考慮的則是對每個點外連的邊分開排。

遺憾的是，在最壞情形下，預處理排序每個點外連的邊仍然需要花費 \(\Theta(\deg(v)\log \deg(v))\) 的時間。因此加總之後得到 \(\Theta(\sum_v\deg(v)\log \deg(v)) = O(m\log (m/n))\)¹。當 \(m=\Omega(n^{1+\epsilon})\) 很大的時候，預處理時間複雜度仍然接近 \(O(m\log n)\)。

姚期智教授發現了，預處理所花費的 \(O(m\log n)\) 時間與實際跑 Borůvka 步驟的 \(O(m+n\log n)\) 時間中間有個間隔！說不定有一個折衷的辦法，放寬預處理時要求每個點外連邊已排序的條件。而在實際跑 Borůvka 步驟的時候，增加一些計算量，但能讓原本的預處理變快。

而我們今天要介紹的這個方法是近乎排序²。它與 Yao 在 1974 年提出的演算法描述過程稍有不同，但對於解決最小生成樹問題來說本質上是一樣的³。

近乎排序 k-almost Sorting

如果一個序列已是近乎排序 (k-almost sorted) 的，那麼代表每個元素距離其排序後的位置，皆嚴格小於 \(k\)。假若我們能將每個點外連的邊都排列成 \(k\)-almost sorted，那麼要找出當前外連邊的最小值（也就是所有可能的候選邊），僅需要從更新後的標記所在之處 \(i_v\) 往後查看至多 \(k\) 條邊即可。換句話說，「可能的候選邊」至多只有 \(k\) 條。

如果我們讓「可能的候選邊」增加到 \(k\) 條之多，那麼引理 MST.8 的部分將會變成 \(O(m + nk\log n)\)。但這麼做有什麼好處呢？近乎排序所需要的時間只需要 \(O(\deg(v)\log \frac{\deg(v)}{k})\) 就好！

引理 MST.10

對於一個長度為 \(n\ge k\) 的陣列，存在一個演算法在 \(O(n\log \frac{n}{k})\) 的時間內將之近乎排序。

引理 MST.10 的證明

有很多方法可以做到這件事情：比方說，我們可以使用做一半的快速排序法，只要遞迴執行到陣列長度不超過 \(k\) 的時候就可以停下來了，這麼一來保證了任何一個數字往右邊數 \(k\) 個以後的所有數字都比較大。由於整個序列 \(n\) 被拆成了 \(O(n/k)\) 段，因此採用找中位數的方式進行遞迴，遞迴的層數只有 \(O(\log \frac{n}{k})\) 這麼多層而已，因此整體時間複雜度為 \(O(n\log\frac{n}{k})\)。

當然，你也可以設計出具有相同效果的合併排序法，這邊就不多贅述了。

把所有度數加起來

接下來，我們可以利用 \(x\log (x/k)\) 是個凸函數的性質，加上延森不等式 Jensen's Inequality 以後可以得到

\[ \begin{aligned} \frac{1}{n}\sum_{v} \deg(v) \log \frac{\deg(v)}{k} &\le \frac{\sum_v\deg(v)}{n} \log \frac{\sum_v\deg(v)}{nk}\\ &= \frac{2m}{n}\log \frac{2m}{nk} \end{aligned} \]

兩邊移項以後就可以得到預處理的時間複雜度 \(O(m\log \frac{m}{nk})\) 了。

借助使用參數 \(k\)，我們能夠使用折衷的手段，以放寬候選邊的數量為代價，加快預處理時間。如此一來，便能在兩者時間複雜度之中取得平衡，降低整體的時間複雜度。

定理 MST.11

Yao's 演算法所需的時間複雜度為 \(O(m\log\log n)\)。

定理 MST.11 的證明

我們根據輸入圖的邊和點數的關聯，分成三種不同的情形選配 \(k\) 之值。

簡單的情況 \(m\ge n\log n\)

我們令 \(k=m/(n\log n)\)，代入以後我們得到預處理時間複雜度 \(O(m\log\log n)\)、實際跑 Borůvka 步驟花的時間為 \(O(m+nk\log n) = O(m)\)，很棒吧！

複雜的情況 \(n \le m < n\log n\)

在這種時候，設定 \(k=m/(n\log n) < 1\) 是沒有意義的。這種時候，我們可以直接先執行不需要預處理的 \(\log\log n\) 次 Borůvka 步驟。根據每次減半的引理 MST.7，不難發現經過了 \(\log\log n\) 次縮連通元件的動作，我們得到一張新的圖 \(G\)：

• 有 \(m' < m\) 條邊、並且
• 有 \(n' \le n/2^{\log\log n} = n/\log n\) 個點。

此時，因為 \(m\ge n\)，我們能保證 \(m / (n'\log n') \ge m/n\ge 1\)，對這個新的圖再次設定 \(k=m/(n'\log n')\) 進行 Yao's 演算法，就能夠達到目的啦！

無聊的情況 \(m < n\)

這個圖要嘛天生就是一棵樹，要嘛就是不連通的。

備註

既然 Yao's 演算法與 Borůvka-Prim 演算法擁有相同的時間複雜度，為什麼仍然想介紹 Yao's 最小生成樹演算法？因為 Yao's 演算法是難得不需要使用費氏堆積也能達到 \(O(m\log\log n)\) 時間的好方法呀！而且，借助費氏堆積我們可以做得更快！

參考資料

• CMU 的 COS423 講義 (2007 年版)