久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

標題: 算法導論學習筆記－第二十一章－用于不相交集合的數據結構 [打印本頁]

作者: 51黑tt 時間: 2016-3-5 18:14
標題: 算法導論學習筆記－第二十一章－用于不相交集合的數據結構
總結：這一章講了并查集的相關概念，以及主要的MAKE-SET, UNION, FIND-SET操作，并給出了并查集的鏈表表示和森林表示方式。

1. 不相交集合上的操作

不相交集合數據結構保持一組不相交的動態集合，每個集合通過一個代表來標識，代表即集合中的某個成員。

一些操作：

MAKE-SET(x): 建立一個新的集合，其唯一成員為x。

UNION(x,y): 將包含x和y的動態集合合并為一個新的集合。

FIND-SET(x): 返回一個指針，指向包含x的集合的代表。

應用：例如，確定一個無向圖中連通子圖的個數。

2. 不相交集合的鏈表表示

每一個集合用一個鏈表表示。每個鏈表中的第一個對象作為它所在集合的代表。

每一個對象的結構：

1）集合成員

2）指向包含下一個集合成員的對象的指針

3）指向代表的指針

每個鏈表都包含head指針和tail指針，head指向鏈表的代表，tail指向鏈表中最后的對象。

MAKE-SET(x): O(1)，創建新鏈表，其僅有對象為x

FIND-SET(x): O(1)，返回x指向代表的指針

UNION(x,y): 將x所在的鏈表拼接到y所在鏈表的表尾。注意，對于原先x所在鏈表中的每一個對象，都需要更新其指向代表的指針。

加權合并啟發式策略：設每個表還包括了表的長度，合并時，總是把較短的表拼到較長的表上。

使用加權合并策略，對m個MAKE-SET, UNION和FIND-SET操作所構成的序列（其中n個MAKE-SET操作，因此UNION操作的次數至多為n-1），花費的總時間為O(m+nlgn)。

3. 不相交集合森林

利用有根樹來表示集合，每棵樹表示一個集合。樹中的每個成員僅指向其父節點，樹的根的父節點仍是自己，且樹的根即集合的代表。

啟發式策略：
1）按秩合并
合并時，使包含較少結點的樹的根指向包含較多結點的樹的根。秩，結點高度的上界。因此，即，具有較小秩的根在UNION操作中要指向具有較大秩的根。

2）路徑壓縮
在FIND-SET操作中，使查找路徑上的每個結點都直接指向根節點。

設rank[x]表示結點的秩，即x的高度的上界，p[x]表示x的父節點

偽代碼
MAKE-SET(x)

p[x] <- x

rank[x] <- 0

偽代碼
UNION(x,y)

LINK(FIND-SET(x),FIND-SET(y))

偽代碼
LINK(x,y)

if rank[x] > rank[y]

then p[y] <- x

else p[x] <- y

if rank[x]=rank[y]

then rank[y] <- rank[y]+1

偽代碼
FIND-SET(x)

if x!=p[x]

then p[x] <- FIND-SET(p[x])

return p[x]

FIND-SET采用了兩趟方法：一趟沿查找路徑上升，直至找到根；第二趟沿查找路徑下降，以便更新每個結點，使之直接指向根。

分析：當同時采用按秩合并和路徑壓縮時，對m個MAKE-SET, UNION, FIND-SET的操作序列，總的運行時間可看作與m成線性關系。

附錄：

view plaincopy to clipboardprint?

typedef struct _node
{
_node* parent;
int rank;
}node;
node *s[5000];
void makeSet(int x)
{
s[x]=new node;
s[x]->rank=0;
s[x]->parent=s[x];
}
node* findSet(node* s)
{
if(s!=s->parent)
{
s->parent=findSet(s->parent);
}
return s->parent;
}
void link(node *s1, node *s2)
{
if(s1==s2)
return;
if(s1->rank > s2->rank)
s2->parent=s1;
else
{
s1->parent=s2;
if(s1->rank==s2->rank)
s2->rank++;
}
}
void _union(node *s1, node *s2)
{
link(findSet(s1),findSet(s2));
}

歡迎光臨 (http://www.zg4o1577.cn/bbs/)