在一些應(yīng)用的問題中，需將n個(gè)不同的元素劃分成一組不相交的集合。開始時(shí)，每個(gè)元素自成一格單元素集合，然后按一定順序?qū)儆谕唤M的元素的集合合并。其間要反復(fù)用到查詢某個(gè)元素屬于哪個(gè)集合的運(yùn)算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集。

1. 并查集的概述

并查集的數(shù)學(xué)模型是一組不相交的動(dòng)態(tài)集合的集合S={A,B,C,...}，它支持以下的運(yùn)算：

(1)union(A,B)：將集合A和B合并，其結(jié)果取名為A或B；

(2)find(x)：找出包含元素x的集合，并返回該集合的名字。

在并查集中需要兩個(gè)類型的參數(shù)：集合名字的類型和元素的類型。在許多情況下，可以用整數(shù)作為集合的名字。如果集合中共有n個(gè)元素，可以用范圍【1：n】以內(nèi)的整數(shù)表示元素。實(shí)現(xiàn)并查集的一個(gè)簡單方法是使用數(shù)組表示元素及其所屬子集的關(guān)系。其中，用數(shù)組下標(biāo)表示元素，用數(shù)組單元記錄該元素所屬的子集名字。如果元素類型不是整型，則可以先構(gòu)造一個(gè)映射，將每個(gè)元素映射成一個(gè)整數(shù)。這種映射可以用散列表或其他方式實(shí)現(xiàn)。

2. 并查集的實(shí)現(xiàn)

采用數(shù)結(jié)構(gòu)實(shí)現(xiàn)并查集的基本思想是，每個(gè)集合用一棵樹表示。樹的結(jié)點(diǎn)用于存儲(chǔ)集合中的元素名。每個(gè)樹結(jié)點(diǎn)還存放一個(gè)指向其父結(jié)點(diǎn)的指針。數(shù)根結(jié)點(diǎn)處的元素代表該數(shù)所表示的集合。利用映射可以找到集合中所對(duì)應(yīng)的數(shù)結(jié)點(diǎn)。

父親數(shù)組是實(shí)現(xiàn)上述數(shù)結(jié)構(gòu)的有效方法。

Java實(shí)現(xiàn)代碼：

public class UnionFind {
 Node[] node; //父親數(shù)組
 //并查集中的結(jié)點(diǎn)
 private static class Node{
 int parent;
 boolean root;
 
 private Node(){
 parent = 1;
 root = true;
 }
 }
 //將每個(gè)元素初始化為一顆單結(jié)點(diǎn)樹
 public UnionFind(int n){
 node = new Node[n + 1];
 for(int e= 0; e <= n; e++){
 node[e] = new Node();
 }
 }
}

find運(yùn)算就是從元素e相應(yīng)的結(jié)點(diǎn)走到樹根處，找出所在集合的名字。

public int find(int e){
 while(!node[e].root){
 e = node[e].parent;
 }
 return e;
 }

union運(yùn)算，合并兩個(gè)集合，只要將表示其中一個(gè)集合的樹的數(shù)根改為表示另一個(gè)集合的樹的數(shù)根的兒子結(jié)點(diǎn)。

public void union(int a, int b){
 node[a].parent += node[b].parent;
 node[b].root = false;
 node[b].parent = a;
 }

3. 快速并查集的實(shí)現(xiàn)

容易看出，在最壞情況下，合并可能使n個(gè)結(jié)點(diǎn)的樹退化成一條鏈，導(dǎo)致對(duì)所有元素各執(zhí)行一次find將耗時(shí)O(n^2)。可做出以下改進(jìn)來加速find運(yùn)算。

1.）小樹合并到大樹

在union操作中，將表示小樹的數(shù)根改為表示大樹的數(shù)根的兒子結(jié)點(diǎn)。于是并查集中每個(gè)結(jié)點(diǎn)至多被移動(dòng)O(logn)次，從而每個(gè)結(jié)點(diǎn)到數(shù)根的距離不會(huì)超過O(logn)。所有，每次find運(yùn)算只需O(logn)時(shí)間。

 /*
 * 合并兩個(gè)集合(加速)
 * 將表示小樹的數(shù)根改為表示大樹的數(shù)根的兒子結(jié)點(diǎn)
 */
 public void union(int a, int b){
 if(node[a].parent < node[b].parent){
 node[b].parent += node[a].parent;
 node[a].root = false;
 node[a].parent = a;
 }else{
 node[a].parent += node[b].parent;
 node[b].root = false;
 node[b].parent = a;
 }
 }

2.）路徑壓縮技術(shù)

在執(zhí)行find時(shí)，實(shí)際上找到了從一個(gè)結(jié)點(diǎn)到數(shù)根的一條路徑。路徑壓縮就是把這條路上所有的結(jié)點(diǎn)都提升1層，以加快找到根結(jié)點(diǎn)的時(shí)間。

 /*
 * find運(yùn)算(加速)
 * 從元素e相應(yīng)的結(jié)點(diǎn)走到樹根處，找出所在集合的名字
 */
 public int find(int e){
 int current = e, p ,gp;
 /*排除當(dāng)前結(jié)點(diǎn)或其父結(jié)點(diǎn)為根的情況后，加速find*/
 if(node[current].root){
 return current;
 }
 p = node[current].parent;
 if(node[current].root){
 return p;
 }
 gp = node[current].parent;
 
 while(true){
 node[current].parent = gp;
 if(node[gp].root){
 return gp;
 }
 current = p;
 p = gp;
 gp = node[p].parent;
 }
 }

 (并查集實(shí)現(xiàn)的詳細(xì)代碼及更多相關(guān)數(shù)據(jù)結(jié)構(gòu)的代碼均在git)

參考資料：

1.《算法設(shè)計(jì)與分析》

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論