并查集的定義ppt課件(已修改)
2025-05-24 08:20 本頁面
【正文】 并 查 集并查集的定義在一些應(yīng)用問題中，我們需要劃分 n個不同的元素成若干組，每一組的元素構(gòu)成一個集合。這種問題的一個解決辦法是，在開始時，讓每個元素自成一個單元素集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并。其間要反復(fù)用到查找一個元素在哪一個集合的運算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集。(給出各個元素之間的聯(lián)系，要求將這些元素分成幾個集合，每個集合中的元素直接或間接有聯(lián)系。在這類問題中主要涉及的是對集合的合并和查找，因此將這種集合稱為并查集。 )并查集的數(shù)學(xué)模型是若干不相交的動態(tài)集合的集合 S＝ {A,B,C,...}，它支持以下的運算：(1)INITIAL(A,x)：構(gòu)造一個取名為 A的集合，它只包含一個元素 x；(2)MERGE(A,B)：將集合 A和 B合并，其結(jié)果取名為 A或 B；(3)FIND(x)：找出元素 x的所在集合，并返回該集合的名字。并查集的數(shù)學(xué)模型例如，對于 S＝ {1,2,...,7}，要求作出 S的等價類劃分滿足給定的等價性條件 :1≡2， 5≡6， 3≡4，和 1≡4。我們首先將 S的每一個元素看成一個等價類，然后順序地處理所列的條件。每處理完一個條件，所得到的相應(yīng)等價類列表如下 :1≡2{1,2}{3}{4}{5}{6}{7}；5≡6{1,2}{3}{4}{5,6}{7}；3≡4{1,2}{3,4}{5,6}{7}；1≡4{1,2,3,4}{5,6}{7}。所得到的結(jié)果是 {1,2,3,4}{5,6}{7}。用數(shù)組實現(xiàn)并查集Constmaxn=100。Vardata:array[1..maxn]ofinteger。在一般情況下， data應(yīng)定義為：array[元素的子界類型 ]of集合名的類型。合并： O(n)查找： O(1)將所有元素合并到一個集合 ： O(n2)建立一個集合 O(1)procedureinitial(A,x:integer)。begindata[x]:=A。end。構(gòu)造一個取名為 A的集合，它只包含一個元素 x；查找一個元素所屬集合 O(1)functionfind(x:integer):integer。beginfind:=data[x]。end。找出元素 x的所在集合，并返回該集合的名字。合并兩個集合 O(n)proceduremerge(A,B:integer)。vari:integer。beginfori:=1tondoifdata[i]=Bthendata[i]:=A。end。將集合 A和 B合并，其結(jié)果取名為 AConstmaxn=100。Vardata:array[1..maxn]ofinteger。procedureinitial(A,x:integer)。begindata[x]:=A。end。functionfind(x:integer):integer。beginfind:=data[x]。end。proceduremerge(A,B:integer)。vari:integer。beginfori:=1tondoifdata[i]=Bthendata[i]:=A。end。用鏈表實現(xiàn)并查集合并： O(i)查找： O(1)將所有元素合并到一個集合 ： O(nlogn)從 n個單元素集開始，至多執(zhí)行 n1次的 MERGE運算就可以將所有元素合并到一個集合中。用 前面 算法，執(zhí)行 n1次 MERGE運算需要 O(n2)時間，效率太低。加速 MERGE運算的一種方法是將各個集合中的元素鏈接成一個表，使得當(dāng)要把集合 B合并到集合 A上去的時候，只要遍歷 B的各個元素而不必遍歷全部 n個元素。但最壞情
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1