并查集路徑壓縮算法改進

文章目錄

• ​​優化find​​
• ​​權重标記（改進merge）​​

大多數情況下，查詢隻關心根節點是誰，并不關心這棵樹的形态，查詢的時候，我們隻要能判斷兩個節點的根節點是否相同即可

但是我們希望查詢過程中，效率能稍微高一些。希望樹能矮一點，這樣我們從某個節點出發找根節點時，會更快速

假如目前的并查集如下，我們需要合并7和8所在樹的根節點，我們從8出發找到根節點1，我們又從7出發經過相同的路徑找到根節點1，然後我們發現根節點相同，不用合并，這樣效率就很低了

優化find

我們進行如下優化：查詢的時候将通路過的每個點的父節點修改成樹根，這樣的方法叫做路徑壓縮

由于無論是查詢還是合并，我們都是操作根節點，修改後樹變矮了，我們查找根節點更快，同時也不影響查詢、合并的結果

查詢的時候将通路過的每個點的父節點修改成樹根，這樣的方法叫做路徑壓縮

int find_root(int x) {
  if (x <= 0 || x >= SIZE) {
    return -1;
  }
  
  // 用于記錄已經周遊過的節點
  vector<int> pos;
  while (x != parent[x]) {
    pos.push_back(x);
    x = parent[x];
  }
  for (int p : pos) {
    parent[p] = x;
  }
  return x;
}

// 遞歸版本的查詢
int cur_find(int x) {
  if (x <= 0 || x >= SIZE) {
    return -1;
  }
  if (x == parent[x]) {
    return x;
  }
  else {
    // 查詢的時候将通路過的每個點的父節點修改成樹根
    parent[x] = cur_find(parent[x]);
    return parent[x];
  }
}      

find執行以後，後面的查詢效率就很好，但美中不足的是，第一次執行find的效率不高，這需要使用權重标記方法優化

權重标記（改進merge）

為什麼會産生上圖那麼高的樹呢？因為我們merge的時候，父子關系一直都是一個方向

void merge(int x, int y) {
  x = cur_find(x);
  y = cur_find(y);
  if (x != y) {
    parent[y] = x; // x永遠是y的父親
    // parent[x] = y;
  }
}      

對于以上的merge代碼，我們如果按照如下的方式輸入，并執行merge，就會産生圖中的樹

7   8
6   7
4   6
2   4
1   2
1   3
1   5      

我們希望在建構并查集的過程中，進行集合合并的時候，能夠使樹能矮一點。我們使用權重标記的方式實作，使用一個height數組，記錄每個節點的層高，下标則表示節點的編号

merge的時候，誰的height大，誰就作為父節點，由于我們隻更新根節點的高度，在矮樹挂在高樹的情況下，根節點的高度不用更新

如果兩棵樹一樣高，根節點合并以後，需要更新作為父親的那棵樹的根節點的height

再像上面一樣輸入，我們merge的時候，就能得到如下結構的并查集

// 合并x和y所在的集合
void merge(int x, int y) {
  x = cur_find(x);
  y = cur_find(y);
  if (x != y) {
    // 這裡x和y都是根節點，誰矮誰作為孩子節點
    if (height[x] > height[y]) {
      parent[y] = x;
    }
    else {
      if (height[x] == height[y]) {
        // y作為合并以後樹的根，根節點高度要+1
        height[y]++;
      }
      parent[x] = y;
    }
  }
}      

用誰高誰當父親的方式merge的時候，我們一直用單個節點往樹中加入，這棵樹一定隻有兩層

從單個節點開始構造并查集，使用誰高誰當父親的方式merge，會得到兩層的樹。我們使用兩個兩層的樹結合，兩個根節點一樣高，我們随便選取一個節點當父親，更新該父節點的height即可（并不是更新所有節點的height），因為我們合并的時候隻看根節點的高度。是以不是什麼時候節點對應的height都是準的，可以保證的是，目前根節點的height是準的

比如我們按照如下的方式構造并查集，就會出現有的節點的height不準确

1   5
1   6
2   3
2   4
1   2