第六章集合與字典PPT課件

1、東南大學(xué)計(jì)算機(jī)學(xué)院東南大學(xué)計(jì)算機(jī)學(xué)院 方效林方效林本課件借鑒了清華大學(xué)殷人昆老師和哈爾濱工業(yè)大學(xué)張巖老師的課件第六章第六章 集合與字典集合與字典本章主要內(nèi)容本章主要內(nèi)容n并查集并查集2并查集并查集n互不相交的集合互不相交的集合 (等價(jià)類的劃分等價(jià)類的劃分)r需要經(jīng)常合并集合需要經(jīng)常合并集合 (等價(jià)類的合并等價(jià)類的合并)r需要經(jīng)常查找元素屬于哪個(gè)集合需要經(jīng)常查找元素屬于哪個(gè)集合3并查集并查集n并查集支持以下操作并查集支持以下操作r初始化初始化UFSets(s): 將將s中每個(gè)元素自成一個(gè)集合中每個(gè)元素自成一個(gè)集合r合并合并Union(Root1,Root2): 集合集合Root2并入并入Root

2、1r查找查找Find(x): 查找元素查找元素x屬于哪個(gè)集合屬于哪個(gè)集合4并查集并查集n用樹表示集合用樹表示集合r初始化時(shí)，每個(gè)元素自成為一棵樹初始化時(shí)，每個(gè)元素自成為一棵樹53412567890全集合全集合S初始化時(shí)形成的森林初始化時(shí)形成的森林初始化時(shí)形成的父指針表示初始化時(shí)形成的父指針表示負(fù)數(shù)表示沒有父結(jié)點(diǎn)負(fù)數(shù)表示沒有父結(jié)點(diǎn)-1表示樹中有表示樹中有1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)-2表示有表示有2個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，以此類推以此類推下標(biāo)下標(biāo)父指針父指針-1-1-1-1-1-1-1-1-1-12345671089并查集并查集n用樹表示集合用樹表示集合r假設(shè)經(jīng)過若干合并后有假設(shè)經(jīng)過若干合并后有3個(gè)集合個(gè)集合0,6,

3、7,8，1,4,9 2,3,568670集合的樹形表示集合的樹形表示集合的父指針表示集合的父指針表示235149下標(biāo)下標(biāo)父指針父指針2345671089-321200-3-401并查集并查集n用樹表示集合用樹表示集合r合并合并s1=0,6,7,8 s2=1,4,9s2作為作為s1根的子樹，或相反根的子樹，或相反78670合并集合合并集合81674908167490第一種合并方式第一種合并方式第二種合并方式第二種合并方式149 第一種合并的父指針表示第一種合并的父指針表示下標(biāo)下標(biāo)父指針父指針2345671089-3202000-700并查集并查集n用樹表示集合用樹表示集合r合并合并s1=0,6,

4、7,8 s2=1,4,9s2作為作為s1根的子樹，或相反根的子樹，或相反哪一種合并方式好？哪一種合并方式好？先介紹查找先介紹查找Find操作操作Find(4)表示4所屬集合，返回值0號(hào)結(jié)點(diǎn)(即根結(jié)點(diǎn))Find操作時(shí)間相當(dāng)于結(jié)點(diǎn)到根路徑長(zhǎng)度881674908167490第一種合并方式第一種合并方式第二種合并方式第二種合并方式第一種方式好：查找時(shí)間更優(yōu)第一種方式好：查找時(shí)間更優(yōu)合并方式：合并方式：將結(jié)點(diǎn)數(shù)更少的集合作為結(jié)點(diǎn)數(shù)更多的集合的根的子樹將結(jié)點(diǎn)數(shù)更少的集合作為結(jié)點(diǎn)數(shù)更多的集合的根的子樹并查集并查集n用樹表示集合用樹表示集合r合并合并s1=0,2,6,7,8 s2=1,4,9令秩表示樹的深度令秩表示樹的深度將秩更小的樹作為秩更大的樹的根的子樹將秩更小的樹作為秩更大的樹的根的子樹98670149 281