1第11章不相交集合類等價關(guān)系與等價類不相交集不相交集的實現(xiàn)不相交集類的實現(xiàn)不相交集的應(yīng)用主要用來解決等價問題2等價關(guān)系對集合中的每一對元素(a,b),a,b∈S,aRb要么是真要么是假，則稱關(guān)系R（relationR）是定義在集合S上。如果aRb為真，則稱a與b相關(guān)。如果集合中的每一對元素不是有關(guān)系就是沒關(guān)系，則稱該關(guān)系（relation）是定義在該集合上的。等價關(guān)系（equivalencerelation）是一種滿足以下三個特性關(guān)系R。自反性（Reflexive）：對所有的a∈R，aRa為真。對稱性（Symmetric）：當(dāng)且僅當(dāng)bRa時，aRb。傳遞性（Transitive）：aRb和bRc隱含aRc。3等價關(guān)系實例親戚關(guān)系就是一個等價關(guān)系。自己和自己是親戚；如果A和B是親戚，則B和A也是親戚；如果A和B是親戚，B和C是親戚，則A和C也是親戚。因此，親戚關(guān)系具有自反性、對稱性和傳遞性，所以是等價關(guān)系。同樣，如果通過公路可以從小鎮(zhèn)a到小鎮(zhèn)b，則稱a與b是有關(guān)系的。如果道路是雙向的，那么公路交通網(wǎng)絡(luò)中的到達(dá)關(guān)系也是一個等價關(guān)系。4等價關(guān)系的基本操作判斷兩個元素之間是否有等價關(guān)系在兩個元素間添加等價關(guān)系5動態(tài)等價問題等價關(guān)系可被表示為布爾型的二維數(shù)組，則可以在常量時間內(nèi)測試等價性。問題在于關(guān)系通常是隱式，而不是顯式定義的例如，一個等價關(guān)系定義在一個五個元素{a1,a2,a3,a4,a5}的集合上。該集合產(chǎn)生25對元素，每一對不是有關(guān)系就是沒有關(guān)系。然而，a1～a2,a3～a4,a1～a5和a4～a2的信息隱含了所有的元素對都是有關(guān)系的。6等價類等價關(guān)系的另一種表示方法是采用等價類集合S中的元素x的等價類是S的一個子集，它包含了所有與x有關(guān)的元素。這些等價類形成了不相交的集合等價類形成了S的一種分割7第11章不相交集合類等價關(guān)系與等價類不相交集不相交集的實現(xiàn)不相交集類的實現(xiàn)不相交集的應(yīng)用主要用來解決等價問題8不相交集合等價類形成了集合S的一種分割。對于任意兩個等價類Si和Sj，Si∩Sj=Φ，將所有的等價類并起來就是集合S。任何兩個子集沒有共同的元素的集合稱為不相交集合。9不相交集合類的基本操作find操作：找出特定元素屬于哪個等價類）union操作：用于添加關(guān)系。如果要把序偶(a,b)加到關(guān)系表中，則與a相關(guān)的元素都與b相關(guān)，與b相關(guān)的元素也都與a相關(guān)。即a的等價類與b的等價類合并為一個等價類。不相交集也稱為并查集10第11章不相交集合類等價關(guān)系與等價類不相交集不相交集的實現(xiàn)不相交集類的實現(xiàn)不相交集的應(yīng)用主要用來解決等價問題11不相交集的實現(xiàn)不相交集的存儲實現(xiàn)不相交集的運(yùn)算實現(xiàn)改進(jìn)的union算法改進(jìn)的find算法12不相交集合類的特點并不關(guān)心元素具體的值，只關(guān)心他們的一個標(biāo)識。因此可簡單將這些元素順序編號為0–N-1在查找操作時，我們并不關(guān)心等價類的名字，只需要知道當(dāng)a和b在一個等價類中時，find的結(jié)果是相同的13解決策略方法一：用線性表保存集合。線性表的第i個元素保存每個第i個元素所屬的等價類名。find是O(1)的。union是線性時間。方法二：用樹保存集合，保證union是常量時間，而查找可以達(dá)到O（logN）14基本的數(shù)據(jù)結(jié)構(gòu)每個等價類表示為一棵樹，等價類的名字為根結(jié)點的名字。這棵樹不一定是二叉樹。整個集合是一片森林因為每個節(jié)點只需要知道父節(jié)點，可以采用雙親表示法，用一個數(shù)組保存。數(shù)組s[i]的值為i的父節(jié)點的下標(biāo)。如s[i]=-1，表示i是某棵樹的根。1501236784591011121314（a）不相交集F01234567891011121314-1000-14-166-19911121216不相交集的實現(xiàn)不相交集的存儲實現(xiàn)不相交集的運(yùn)算實現(xiàn)改進(jìn)的union算法改進(jìn)的find算法17基本操作的實現(xiàn)為了執(zhí)行兩個集合的union操作，我們歸并這兩棵樹，將一棵樹的根作為另一棵樹的孩子。這個操作很明顯是常量時間。元素x的find操作返回包含x的樹的根。完成該操作的時間正比于從x到根的路徑上的結(jié)點數(shù)。最壞情況可能是O(N)。1801236784591011121314（a）不相交集F01234567891011121314-1000-14-166-199111212例如：查找12所屬的子集將4和6歸并起來19不相交集的實現(xiàn)不相交集的存儲實現(xiàn)不相交集的運(yùn)算實現(xiàn)改進(jìn)的union算法改進(jìn)的find算法20改進(jìn)的union算法盡管不相交集的union操作性能很好，而find操作的性能不佳。但find操作的性能問題是由union操作引起的。是union操作實現(xiàn)時沒有關(guān)心所構(gòu)造的樹的結(jié)構(gòu)。在極端的情況下，union操作可能使樹蛻化為線性表。改進(jìn)的思想：盡量避免樹的增高按規(guī)模并按高度并21按規(guī)模歸并將規(guī)模小的樹作為規(guī)模大的樹的子樹，對規(guī)模相同的樹可以任意選擇例如歸并4和9，如將9作為4的子樹，形成一棵高度為5的樹。但將4作為9的子樹，形成的樹高度還為401236784591011121314（a）不相交集F22按規(guī)模并的最壞情況每次都是歸并兩個等規(guī)模的集合。每歸并一次，高度增加一層。23按規(guī)模并的實現(xiàn)需要記錄每棵樹的規(guī)模解決方法：使根的數(shù)組項包含一個負(fù)的樹規(guī)模。執(zhí)行union操作時，先檢查規(guī)模，再決定誰并到誰2401236784591011121314（a）不相交集F01234567891011121314-4000-24-366-699111212執(zhí)行union（4，9）01234567891011121314-400094-366-89911121225按高度歸并記錄了樹的高度而不是樹的規(guī)模，通過將較淺的樹作為較深的樹的子樹完成歸并操作。保證了對數(shù)的find操作2601236784591011121314（a）不相交集F01234567891011121314-2000-24-266-499111212執(zhí)行union（4，9）01234567891011121314-200094-266-49911121227不相交集的實現(xiàn)不相交集的存儲實現(xiàn)不相交集的運(yùn)算實現(xiàn)改進(jìn)的union算法改進(jìn)的find算法28改進(jìn)的find算法不相交集中，每棵子樹的最理想的狀態(tài)是一棵二層的數(shù)，只有根結(jié)點和它的兒子。這時，find操作的效率最高。改進(jìn)的union算法可以降低樹的高度，提高find的效率。但當(dāng)被歸并的兩棵樹規(guī)模相同或高度相同時，樹高還是會增加。另外一種效率的改進(jìn)方法是通過find操作，這種方法稱為路徑壓縮。

29路徑壓縮當(dāng)對find（x）采用路徑壓縮方法的話，那么在從x到根結(jié)點的路徑上的每一個結(jié)點都將自己的父結(jié)點改為根結(jié)點。如果x是一個很深的結(jié)點，這一改進(jìn)將會大大降低樹的高度路徑壓縮能與按規(guī)模歸并完美地兼容。路徑壓縮與按高度歸并不完全兼容，3001236784591011121314find（14）前01236784591011121314find（14）后31第11章不相交集合類等價關(guān)系與等價類不相交集不相交集的實現(xiàn)不相交集類的實現(xiàn)不相交集的應(yīng)用主要用來解決等價問題32不相交集類的實現(xiàn)采用按規(guī)模并和路徑壓縮classDisjointSet{private:intsize; int*parent;public:DisjointSet(ints); ~DisjointSet(){delete[]parent;} voidUnion(introot1,introot2); intFind(intx);};33構(gòu)造函數(shù)的定義DisjointSet::DisjointSet(intn){size=n;parent=newint[size];

for(inti=0;i<size;++i)parent[i]=-1;}34Find函數(shù)的實現(xiàn)intDisjointSet::Find(intx){if(parent[x]<0)returnx;returnparent[x]=Find(parent[x]);}如何在查找的過程中改變結(jié)點的父結(jié)點35Union函數(shù)的實現(xiàn)voidDisjointSet::Union(introot1,introot2){if(root1==root2)return;if(parent[root1]>parent[root2]){parent[root2]+=parent[root1];parent[root1]=root2;}else{parent[root1]+=parent[root2];parent[root2]=root1;}}36第11章不相交集合類等價關(guān)系與等價類不相交集不相交集的實現(xiàn)不相交集類的實現(xiàn)不相交集的應(yīng)用主要用來解決等價問題37不相交集的應(yīng)用迷宮問題最近共同祖先問題38應(yīng)用—迷宮問題把迷宮看成由M×N個矩形單元組成，入口在左上角，出口在右下角。左上角的單元與右下角的單元是連通的，單元之間用墻隔開。一個5×5的迷宮012345678910111213141516171819202122232439生成迷宮的算法開始時假設(shè)所有的地方都有墻（除了入口和出口），所有的單元都不連通。我們不斷地隨機(jī)選擇一堵墻，如果由該墻分割的單元互相之間沒有連通，則把墻拆除。重復(fù)上述過程，直到連通了入口和出口，就得到了一個迷宮。繼續(xù)拆墻直到從每一個單元都能到達(dá)其他任一單元當(dāng)然更好，因為這樣做會在迷宮中生成更多的錯誤路徑40實現(xiàn)如果把連通看成一個關(guān)系，則該關(guān)系是一個等價關(guān)系。迷宮問題轉(zhuǎn)化成等價類的歸并問題。開始時，每個單元是一個等價類。選擇相鄰兩個單元，判別是否在一個等價類。如果不是，敲開兩個單元之間的墻，使之連通。歸并兩個等價類。重復(fù)上述過程，直到所有單元都在一個等價類中。41初始的配置某些墻已經(jīng)被拆除。此時，如果我們隨機(jī)選擇8和13之間的墻，這堵墻不用拆掉，因為8和13已經(jīng)連通我們隨機(jī)選擇了18和13之間的墻；因為18和13沒有連通，這堵墻被拆除42迷宮生成voidcreatePuzzle(intsize)//size為迷宮的規(guī)模{intnum1,num2;DisjointSetds(size*size);srand(time(0));while(ds.Find(0)!=ds.Find(size*size-1)){while(true){//選擇兩個相鄰的不連通單元

num1=rand()*size*size/(RAND_MAX+1);num2=num1-size;//檢查上方的單元

if(num2>=0)if(ds.Find(num1)!=ds.Find(num2))break;num2=num1-1;//檢查左邊的單元

if(num1%size!=0)if(ds.Find(num1)!=ds.Find(num2))break;num2=num1+size;//檢查下方的單元

if(num2<size*size)if(ds.Find(num1)!=ds.Find(num2))break; num2=num1+1;//檢查右邊的單元

if(num2%size!=0)if(ds