Union-Find

source:
Coursera Algorithms, Part 1
Algorithms, 4th ed. - [Sedgewick, Wayne]


什麼是 Union-Find

  • 尋找一批 object 中的任兩個 object 是否在同一群
  • 同一群的 object 間,有路可以找到彼此
  • 路表示 object 之間的連結
  • 兩個不同群的 object 間,找不到路可以通到對方

為什麼要知道 Union-Find

  • 應用環境
    • 圖片畫素
    • 網路節點
    • 社交軟體的朋友關係
    • 電路晶體

Union(連結)的建立

  • 每個 object 都給一個編號
  • 假設有 N 個 object ,編號從 0~N-1
  • 用 connect(a, b) 表示連結編號 a 和編號 b
    • ex: connect(3, 10) 表示連結 object 3 和 object 10

如何判斷在同一群

  • 儲存連結的方式影響判斷的速度
  • list
    • 有關係的 object 串在同一個list中
    • 判斷兩個 object 是否在同一個list中
  • array
    • 每個 object 都有一個標籤
    • 判斷兩個 object 的標籤一不一樣
  • array 比較快,因為只要比較一次 (quick-find)

如何用array儲存 - 建立 array

  • 標籤建立時使用對應 object 的編號
object 0 1 2 N-1
標籤 0 1 2 N-1

如何用array儲存 - 建立連結

  • 連結在一起的 object 把標籤改成一樣

    • 假設改成跟第二個 object 一樣
  • connect(1,3)

object 0 1 2 3
標籤 0 3 2 3
  • connect(3,2)
object 0 1 2 3
標籤 0 2 2 2

成本

  • 讀寫 array 的次數
  • 連結兩個 object 時就要把整個 array 走一次,才能確保該改的標籤都有改到
  • 若是對
    N
    個 object 做
    N
    次連結,就需要
    N2
    次讀寫
  • Slow!
方法 建立 連結 判斷
quick-find
N
N
1

改進 - 連結成本

  • 用樹狀的方式連結 (quick-union)
  • 標籤改成代表 parent object

  • object 標籤與 object 編號一樣時表示 object 是一個 root
  • 連結兩個 object 等於把兩個 object 所在的 tree 合併成一個 tree

樹狀 array - 建立

  • 標籤建立時每個 object 就是一個 root
object 0 1 2 N-1
標籤 0 1 2 N-1

樹狀 array - 連結

  • 假設使用第二個 object 的 root 當作新的 root

  • connect(1,3)
object 0 1 2 3 4
標籤 0 3 2 3 4
  • connect(0,4)
object 0 1 2 3 4
標籤 4 3 2 3 4

  • connect(1,0)
    • object 1 root = object 3
    • object 0 root = object 4
object 0 1 2 3 4
標籤 4 3 2 4 4

成本

  • 最差的情況下樹的深度可能跟 object 數量一樣
    • unbalanced tree
  • 連結時找 root 的讀寫次數與深度有關
    • 最多
      N
  • 以 object root 是否相同判斷有沒有在同一群
    • 也跟樹的深度相關
    • 最多
      N

  • Slow too!
方法 建立 連結 判斷
quick-find
N
N
1
quick-union
N
N
N

改進 - 避免樹長太深

  • 紀錄樹的深度 (weighted quick-union(QU))
  • 連結時把矮的樹並到高的樹中
    • 減緩樹變深的速度

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →


  • 樹的深度最多是
    log2N
  • 為什麼?

原因

  • 要讓 tree x 深度+1,tree x 就必須跟至少跟自己一樣長的 tree y 合併
  • 深度每+1,樹包含的 object 數量就 double
  • N
    個 object 最多只能 double
    log2N

成本

方法 建立 連結 判斷
quick-find
N
N
1
quick-union
N
N
N
weighted QU
N
log2N
log2N

改進 - 讓樹更扁

  • 找 object 的 root 時,順手把所有經過的 object 都往上提兩層 (path compression)
    • 把 parent object 改成 grand parent object
    • 找到 root 後,原本 object 所在的深度就會減半

成本

  • 專家說會變成
    Nlog2N
    • log2N
      = 對
      N
      重複做
      log2
      1
      的次數 (Iterated logarithm)
    • log265536
      = 4
    • log265536=16
      ,
      log216=4
      ,
      log24=2
      ,
      log22=1

方法 建立 連結 判斷
quick-find
N
N
1
quick-union
N
N
N
weighted QU (WQU)
N
log2N
log2N
WQU & path compression
N
log2N
log2N