堆與互不相交集課件-資料下載頁
2025-07-21 13:47本頁面
【正文】 1 u=FIND(x)。 y=FIND(y) 2 if rank(u)?rank(v) then 3 p(u)=v 4 if rank(u)=rank(v) then rank(v)=rank(v)+1 5 else p(v)=u 6 end if 不相交集 算法 FIND 輸入：節(jié)點 x 輸出： root(x)是包含 x的樹根 1 y=x 2 while p(y)?null 3 y=p(y) 4 end while 5 root=y。y=x 6 while p(y)?null 7 w=p(y)。 p(y)=root。y=w。 8 end while 9 return root 不相交集 ? 路徑壓縮舉例 設 S={1， 2， 3， 4， 5， 6， 7， 8， 9}，考慮用下面合并和尋找序列： UNION(1， 2)， UNION(3， 4)， UNION(5， 6)， UNION(7， 8)，UNION(2， 4)， UNION(8， 9)， UNION(6， 8)， FIND(5)， UNION(4，8)， FIND(1) 1 3 4 5 2 6 7 8 9 2 6 8 9 4 1 3 5 7 2 6 8 9 4 1 3 5 7 2 6 8 9 4 1 3 5 7 (a) (b) (d) (c) 不相交集 2 6 8 9 4 1 3 5 7 (e) 2 6 8 9 4 1 3 5 7 (f) 不相交集 ? UNIONFIND算法的分析 引理 ：對于任意的整數(shù) ，秩 節(jié)點數(shù)至多是 。 推論 ：任何節(jié)點的秩最大是 。 例如， 定理 ：連續(xù)執(zhí)行 次 NUION和 FIND運算，在最壞情況 下，所需要執(zhí)行時間是 。 其中， 定義為： )(mO0?r r rn2? ?nlogm)()lo g( * mOnmO ?n*log?n*log ?0 1,0?n}1l o gl o gl o g0m i n { ?? ni ? 2?n52l o g,42l o g,32l o g,22l o g,12l o g 65536*16*4*2** ????? 。在幾乎所有的實際應用中， 。所以，它所需要的執(zhí)行時間實際上將是 。 5log* ?n? 共 i個
法律信息相關推薦
鄂ICP備17016276號-1