[理學(xué)]數(shù)據(jù)結(jié)構(gòu)ppt第八章(已修改)
2024-10-31 00:45 本頁(yè)面
【正文】 1 ? 并查集 ? 靜態(tài)搜索表 ? 二叉搜索樹(shù) ? AVL樹(shù) 2 并查集 (UnionFind Sets) ? 并查集支持以下三種操作： ? Union (Root1, Root2) //合并操作 ? Find (x) //搜索操作 ? InitUFSets (s ) //初始化操作 ? 對(duì)于并查集來(lái)說(shuō)，每個(gè)集合用一棵樹(shù)表示。 ? 為此，采用 樹(shù)的雙親表示 作為集合存儲(chǔ)表示。集合元素的編號(hào)從 0到 n1。其中 n 是最大元素個(gè)數(shù)。 3 ? 在 雙親表示 中， 第 i 個(gè)數(shù)組元素代表包含集合元素 i 的樹(shù)結(jié)點(diǎn) 。初始時(shí) , 根結(jié)點(diǎn)的雙親為 1，表示集合中的元素個(gè)數(shù)。 ? 在同一棵樹(shù)上所有結(jié)點(diǎn)所代表的集合元素在同一個(gè)子集合中。 ? 為此，需要有兩個(gè)映射： ? 集合元素到存放該元素名的樹(shù)結(jié)點(diǎn)間的對(duì)應(yīng)； ? 集合名到表示該集合的樹(shù)的根結(jié)點(diǎn)間的對(duì)應(yīng)。 4 ? 設(shè) S1= {0, 6, 7, 8 }, S2= { 1, 4, 9 }, S3= { 2, 3, 5 } 集合名 指針 0 S1 1 S2 2 S3 0 4 2 7 6 8 1 9 3 5 ? 為簡(jiǎn)化討論 ， 忽略實(shí)際的集合名 ， 僅用表示集合的樹(shù)的根來(lái)標(biāo)識(shí)集合 。 5 ? 初始時(shí) , InitUFSets(S) 構(gòu)造一個(gè)森林 , 每棵樹(shù)只有一個(gè)結(jié)點(diǎn) , 表示集合中各元素自成一個(gè)子集合 S[i] = 1, i = 0, 1, … , n1。 ? 用 Find(S, i) 尋找集合元素 i 的根 。 ? 如果有兩個(gè)集合元素 i 和 j: Find(S, i) == Find(S, j) 表明這兩個(gè)元素在同一個(gè)集合中 ， ? 如果兩個(gè)集合元素 i 和 j 不在同一個(gè)集合中 ,可用 Union(S, i, j) 將它們合并到一個(gè)集合中 。 6 S1 下標(biāo) parent 集合 S1, S2 和 S3 的雙親表示 4 4 3 2 3 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 7 6 8 4 1 9 2 3 5 S2 S3 7 S1 ? S2的可能的表示方法 下標(biāo) parent 集合 S1 ? S2 和 S3 的雙親表示 7 4 3 2 0 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 7 6 8 4 1 9 4 1 9 0 8 7 6 8 并查集的結(jié)構(gòu)定義 const int SetSize = 50。 //并查集元素個(gè)數(shù) typedef struct { //并查集結(jié)構(gòu)定義 int parent[SetSize]。 //集合元素?cái)?shù)組 } UFSets。 void InitUFSets (UFSets *S) { //集合初始化 for ( int i = 0。 i SetSize。 i++ ) Sparent[i] = 1。 } //每一個(gè)自成一個(gè)單元素集合 9 ? 并查集操作的算法 ? 查找 5 0 1 2 3 0 1 2 3 4 Find (S,4) Find (S,3) = 3 Find (S,2) =2 Find (S,1) = 1 Find (S,0) = 0 = 5 0 結(jié)束 10 int Find (UFSets * S, int x ) { if ( Sparent [x] 0 ) return x。 else return Find (S, Sparent [x] )。 } 5 0 1 2 3 parent Parent[4] =3 Parent[3] =2 Parent[2] =1 Parent[1] =0 Parent[0] =5 0 1 2 3 4 11 void Union (UFSets *S, int Root1, int Root2) { //求兩個(gè)不相交集合 Root1與 Root2的并 Sparent[Root1] += Sparent[Root2]。 Sparent[Root2] = Root1。 //將 Root2連接到 Root1下面 } ? Find和 Union操作性能不好。假設(shè)最初 n 個(gè)元素構(gòu)成 n 棵樹(shù)組成的森林， Sparent[i] = 1。做處理 Union(n2, n1), …, Union(1, 2), Union(0, 1)后，將產(chǎn)生退化的樹(shù)。 12 ? 合并 1 1 1 1 1 0 2 3 4 3 5 0 3 2 1 3 3 4 1 3 3 2 2 0 2 3 1 4 Union(0,1) 2 3 4 1 4 2 1 2 3 4 Union(1,2) Union(2,3) Union(3,4) 13 ? 執(zhí)行一次 Union操作所需時(shí)間是 O(1)， n1次 Union操作所需時(shí)間是 O(n)。 ? 若再執(zhí)行 Find(0), Find(1), …, Find(n1), 若被搜索的元素為 i，完成 Find(i) 操作需要時(shí)間為 O(i)， 完成 n 次搜索需要的總時(shí)間將達(dá)到 ? 改進(jìn)的方法 ? 按樹(shù)的結(jié)點(diǎn)個(gè)數(shù)合并 ? 按樹(shù)的高度合并 ? 壓縮元素的路徑長(zhǎng)度 ???nini12OO )()(14 ? 按樹(shù)結(jié)點(diǎn)個(gè)數(shù)合并 ?結(jié)點(diǎn)個(gè)數(shù)多的樹(shù)的根結(jié)點(diǎn)作根 1 1 1 1 1 0 1 2 3 4 1 1 0 7 2 5 6 5 2 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) 15 void WeightedUnion (UFSets *S, int Rt1, int Rt2 ) { //按 Union的加權(quán)規(guī)則改進(jìn)的算法 int temp = Sparent[Rt1] + Sparent[Rt2]。 if ( Sparent[Rt2] Sparent[Rt1] ) { Sparent[Rt1] = Rt2。 //Root2中結(jié)點(diǎn)多 Sparent[Rt2] = temp。 //Root1指向 Root2 } else { Sparent[Rt2] = Rt1。 //Root1中結(jié)點(diǎn)多 Sparent[Rt1] = temp。 //Root2指向 Root1 } } 16 ? 按樹(shù)高度合并 ? 高度高的樹(shù)的根結(jié)點(diǎn)作根 0 0 0 0 0 0 1 2 3 4 0 0 0 2 2 5 6 2 1 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) 17 Union操作的折疊規(guī)則 ? 為進(jìn)一步改進(jìn)樹(shù)的性能 ， 可以使用如下折疊規(guī)則來(lái) “ 壓縮路徑 ” 。 即： 如果 j 是從 i 到根 root 的 路 徑 上 的 一 個(gè) 結(jié) 點(diǎn) ， 且 Sparent[j] != root[j]， 則把 Sparent[j] 置為 root[i]。 0 0 6 7 8 6 7 8 1 9 1 9 3 5 3 5 從 i = 5 壓縮路徑 18 int CollapsingFind (UFSets *S, int i ) { //使用折疊規(guī)則的搜索算法 int j = i。 while ( Sparent[j] = 0 ) j = Sparent[j]。 //讓 j 循雙親指針走到根 while ( i != j ) { //換 parent[i] 到 j int temp = Sparent[i]。 Sparent[i] = j。 i = temp。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1