連通性問題 問題概述 先來看一張圖： 在這個彼此連接和斷開的點網絡中，我們可以找到一條 p 點到 q 點的路徑。在計算機網絡中判斷兩臺主機是否連通、在社交網絡中判斷兩個用戶是否存在間接社交關系等，都可以抽象成連通性問題。 問題抽象 可將網絡中的點（主機、人）抽象為對象，p-q 表示 p連接到q，連通關系可傳遞： p-q & q-r => p-r；為簡述問題，將兩個對象標記為一個整數對，則給定整數對序列就能描述出點網絡。 如下圖結點數 N = 5 的網絡（使用 0 ~ N-1表示對象），可用整數對序列 0-1 1-3 2-4 來描述連通關系， 其中 0 和 3 也是連通的，存在兩個連通分量：{0, 1, 3} 和 {2, 4} 問題：給定描述連通關系的整數對序列，任給其中兩個整數 p 和 q，判斷其是否能連通？ 問題示例 ~~~ 輸入 不連通 連通 3-4 3-4 4-9 4-9 8-0 8-0 2-3 2-3 5-6 5-6 2-9 2-3-4-9 5-9 5-9 7-3 7-3 4-8 4-8 5-6 5-6 0-2 0-8-4-3-2 6-1 6-1 ~~~ 對應的連通圖如下，黑線表示首次連接兩個結點，綠線表示兩結點已存在連通關系： 算法一：快速查找算法 使用數組 id[i] 存儲結點的值， i 為結點序號，即初始狀態序號和數組值相同 ： 當輸入前兩個連通關系后， id[i] 變化如下： 可以看出， id[i] 的值是完成連通后，i 連接到的終點結點。若 p 和 q 連通，則 id[p] 和 id[q] 值應相等。 如完成 4-9 后， id[3] 和 id[4] 的值均為終點結點 9。此時判斷 3 和 9 是否連通，直接判斷 id[3] 和 id[9] 的值是否相等，相等則連通，不等則不存在連通關系。顯然 id[3] == id[9] == 9，即存在連通關系。 算法實現 ~~~ /** file: 1.1-quick_find.go */ package main import ... const N = 10 var id [N]int func main() { reader := bufio.NewReader(os.Stdin) // 初始化 id 數組，元素值與結點序號相等 for i := 0; i < N; i++ { id[i] = i } // 讀取命令行輸入 for { data, _, _ := reader.ReadLine() str := string(data) if str == "\n" { continue } if str == "#" { break } values := strings.Split(str, " ") p, _ := strconv.Atoi(values[0]) q, _ := strconv.Atoi(values[1]) if Connected(p, q) { fmt.Printf("Already Connected nodes: %d-%d\n", p, q) continue } Union(p, q) } } // 判斷整數 p 和 q 的結點是否連通 func Connected(p, q int) bool { return id[p] == id[q] } // 連通 p-q 結點 func Union(p, q int) { pid := id[p] qid := id[q] // 遍歷 id 數組，將所有值為 id[p] 的結點全部替換為 id[q] for i := 0; i < N; i++ { if id[i] == pid { id[i] = qid } } fmt.Printf("Unconnected nodes: %d-%d\n", p, q) } 運行效果：能判斷 2-9 已存在連通關系 ~~~ 復雜度 快速查找算法在判斷 p 和 q 是否連通時，只需判斷 id[p] 和 id[q] 是否相等。但 p 和 q 不連通時會進行合并，每次合并都需要遍歷整個數組。特性：查找快、合并慢 算法二：快速合并算法 概述 快速查找算法每次合并都會全遍歷數組導致低效。我們想能不能不要每次都遍歷 id[] ，優化為每次只遍歷數組的部分值，復雜度都會降低。 這時應想到樹結構，在連通關系的傳遞性中，p->r & q->r => p->q，可將 r 視為根，p 和 q 視為子結點，因為 p 和 q 有相同的根 r，所以 p 和 q 是連通的。這里的樹是連通關系的抽象。 數據結構 使用數組作為樹的實現： 結點數組 id[N]，id[i] 存放 i 的父結點 i 的根結點是 id[id[...id[i]...]]，不斷向上找父結點的父結點...直到根結點（父結點是自身） 使用樹的優勢 將整數對序列的表示從數組改為樹，每個結點存儲它的父結點位置，這種樹有 2 點好處： 判斷 p 和 q 是否連通：是否有相同的根結點 合并 p 到 q：將 p 的根結點改為 q 的根結點（無需全遍歷，快速合并） 例子： 對于上邊的整數對序列，查找、合并過程如下，橙色是合并動作、灰色是已連通狀態、綠色是存儲樹的數組。 注意紅色的 2-3，不是直接把 2 作為 3 的子結點，而是找到 3 的根結點 9，合并 2-3 與 3-4-9 ，生成 2-9 算法實現： ~~~ /** file: 1.2-quick_union.go */ // p 和 q 有相同的根結點，則是連通的 func Connected(p, q int) bool { return getRoot(p) == getRoot(q) } // 連通 p-q 結點 func Union(p, q int) { pRoot := getRoot(p) qRoot := getRoot(q) id[pRoot] = qRoot // q 樹的根此時有了父結點（p 樹的根），完成合并 fmt.Printf("Unconnected nodes: %d-%d\n", p, q) } // 獲取結點 i 的根結點 func getRoot(i int) int { // 沒到根結點就繼續向上尋找 for i != id[i] { i = id[i] } return i } ~~~ 算法三：帶權快速合并算法 概述 快速合并算法有一個缺陷：數據量很大時，任意合并子樹，會導致樹越來越高，在查找根結點時要遍歷數組大部分的值，依舊會很慢。下圖中判斷 p、q 是否連通，就需要查找 13 個結點： 如果樹合并后的依舊比較矮，各子樹之間平衡，則查找根結點會少遍歷很多結點，下圖中再判斷 p、q 是否連通，只需查找 7 個結點： 平衡樹的構建 構建平衡的樹需要在合并時，將小樹合并到大樹上，保證合并后的樹增高緩慢或者就不增高，從而使大部分的合并需要遍歷的結點大大減少。區分小樹、大樹使用的是樹的權值：子樹含有結點的個數。 數據結構 樹結點的存儲依舊使用 id[i] ，但需要一個額外的數組 size[i]，記錄結點 i 的子結點數。 算法實現 ~~~ /** file: 1.3-weighted_version.go 在快速合并算法的基礎上，只需要在合并操作中，將小樹合并到大樹上即可 */ var id [N]int var size [N]int func main() { // 初始化 id 數組，元素值與結點序號相等 for i := 0; i < N; i++ { id[i] = i size[i] = i } ... } ... // 連通 p-q 結點 func Union(p, q int) { pRoot := getRoot(p) qRoot := getRoot(q) // p 樹是大樹 if size[pRoot] < size[qRoot] { id[pRoot] = qRoot size[qRoot] += size[pRoot] } else { id[qRoot] = id[pRoot] size[pRoot] += size[qRoot] } id[pRoot] = qRoot // q 樹的根此時有了父結點（p 樹的根），完成合并 fmt.Printf("Unconnected nodes: %d-%d\n", p, q) } ~~~ 算法四：路徑壓縮的加權快速合并算法 概述 加權快速合并算法在大部分整數對都是直接連接的情況下，生成的樹依舊會比較高，比如序列： ~~~ 10-8 8-6 11-9 12-9 9-6 6-3 7-3 3-1 4-1 5-1 1-0 2-0 ~~~ 生成的樹如下： 此時判斷 9-2 的連通關系，需要分別找到 9 和 2 的根結點。在尋找 9 的根結點時經過 6、3、1樹，因為6、3、1樹的子節點和 9 一樣，根結點都是 0，所以直接把6、3、1樹變成 0 的子樹。如下： 優化 每次計算某個節點的根結點時，將沿路檢查的結點也指向根結點。盡可能的展平樹，在檢查連通狀態時將大大減少遍歷的結點數目。 算法實現 ~~~ /** file: 1.4-path_compression_by_halving.go 改動的代碼很少，但很精妙 */ // 獲取結點 i 的根結點 func getRoot(i int) int { // 沒到根結點就繼續向上尋找 for i != id[i] { id[i] = id[id[i]] // 將結點、結點的父結點不斷往上挪動，直到都連接上了根結點 i = id[i] } return i } ~~~ 復雜度 N 是結點集合的大小，T 是樹的高度。 算法 初始化的復雜度 合并復雜度 查找復雜度 快速查找 N N（全遍歷） 1（數組取值對比） 快速合并 N T（遍歷樹） T（遍歷樹） 帶權快速合并 N lg N lg N 路徑壓縮的帶權快速合并 N 接近1（樹的高度幾乎為2） 接近1 總結 上邊介紹了 4 種解決連通性問題的算法，從低效完成基本功能的快速查找，到不斷優化降低復雜度接近1 的路徑壓縮帶權快速合并。可以學到算法解決程序問題的大致步驟：先完成基本功能，再針對低效操作來優化降低復雜度。 原文：https://wuyin.io/2018/01/27/c... 本文來自：Segmentfault