推 yoco315:推薦這篇文章 03/23 17:47
> -------------------------------------------------------------------------- <
作者: SHANGOYANYI () 看板: C_and_CPP
標題: Re: 有關Kruskal演算法語法的問題
時間: Thu Mar 23 15:23:52 2006
其實單純要維持集合關係也可以用ary
以原po的7個node來說
開一個size為8的ary
index=0~7 0不用(方便表示而已 囧)
然後把i=0~7令a[i]=i; //表示指到自己 也就是代表自己是root
現在假設{1,3,6}在同一個set
那就把3跟6的內容改成1
這樣在找3的root時候看到a[3]內容是1 就知道3上面有1
然後再看a[1]的內容 這時候a[1]的內容是1 表示node_1是3的root
圖:
1
↗ ↖
3 6
實際:
index 0 1 2 3 4 5 6 7
value 0 1 2 1 4 5 1 7
再假設{2,5}在同一個set
那就是a[5]=2;
圖:
2
↗
5
實際:
index 0 1 2 3 4 5 6 7
value 0 1 2 1 4 2 1 7
好啦 現在有4個set分別是{1,3,6},{2,5},{4},{7}
假設下一個要檢查的邊是(6,1)
那從6去往上trace會找到1 從1往上trace也會找到1
所以1跟6是在同一個set中
接下來假設要檢查的邊是(2,3)
從3往上trace會找到1
從2往上trace會找到2
因為兩個找到不同的root 所以是在不同的set中
那就可以把這個edge加入 然後把兩個set做聯集
聯集的作法就是a[2]=1就好了
圖:
1
↗↑↖
2 3 6
↗
5
實際:
index 0 1 2 3 4 5 6 7
value 0 1 1 1 4 2 1 7
一般化的話就是find(a,b)
a,b分別一路找到自己的root 假設為p,q
若p==q 則a,b在同一set
若p!=q 則a,b在不同set 可將E(G)=(a,b)加入 然後令a[q]=p
我自己是覺得這樣做好像也可以@@"
※ 引述《huangwh (香腸)》之銘言：
: 你是說 3的媽媽為2
: 2的媽媽為1
: 最後 1 的媽媽就是6
: 也就是(6,1)
: 是這樣子嗎?
: 方便用我原本的例子
: 來講解一下可以嗎?
: 謝謝
: 但是我就是不知道要怎將這斷語法用c++寫出來~!!
不考慮效率什麼的問題的話
最簡單的方法就是:
假設你有七個點好了
那就 maintain 7 個 circular link list
初始值就是大家指著自己
０┐ １┐ ２┐ ３┐ ４┐ ５┐ ６┐
↑│ ↑│ ↑│ ↑│ ↑│ ↑│ ↑│
└┘ └┘ └┘ └┘ └┘ └┘ └┘
next
operation 有分兩類,
一個是把 (x, y) 歸成同一類
這裡稱之為 Union(x,y)
一個是查 (x, y) 是否為同一類
這裡稱之為 isSameGroup(x,y)
每次先查查他們在不在同一個 group (用 isSameGroup(x,y))
如果已經在同一個 group 了, 就 ignore, 就是你 * 的那類
否則就用 Union(x,y) 把他們組合起來
(5,0)
把 5 拿出來, 它現在是:
順著它的 next link 往下走
５┐ 直到走回自己都沒有看到 0
↑│ 所以 isSameGroup(5,0) 就是 false
└┘ 我們就要進行 Union(5,0) 的動作
┌─┐
│ ↓
０ ５ １┐ ２┐ ３┐ ４┐ ６┐
↑ │ ↑│ ↑│ ↑│ ↑│ ↑│
└─┘ └┘ └┘ └┘ └┘ └┘
(3,2)
把 3 拿出來, 它現在是:
順著它的 next link 往下走
３┐ 直到走回自己都沒有看到 2
↑│ 所以 isSameGroup(3,2) 就是 false
└┘ 我們就要進行 Union(3,2) 的動作
┌─┐ ┌─┐
│ ↓ │ ↓
０ ５ ２ ３ １┐ ４┐ ６┐
↑ │ ↑ │ ↑│ ↑│ ↑│
└─┘ └─┘ └┘ └┘ └┘
(6,1)
把 6 拿出來, 它現在是:
順著它的 next link 往下走
６┐ 直到走回自己都沒有看到 1
↑│ 所以 isSameGroup(6,1) 就是 false
└┘ 我們就要進行 Union(6,1) 的動作
┌─┐ ┌─┐ ┌─┐
│ ↓ │ ↓ │ ↓
０ ５ ２ ３ １ ６ ４┐
↑ │ ↑ │ ↑ │ ↑│
└─┘ └─┘ └─┘ └┘
(2,1)
把 2 拿出來, 它現在是:
┌─┐
│ ↓ 順著它的 next link 往下走
２ ３ 直到走回自己都沒有看到 1
↑ │ 所以 isSameGroup(2,1) 就是 false
└─┘ 我們就要進行 Union(2,1) 的動作
┌─┐ ┌─┐ ┌─┐
│ ↓ │ ↓ │ ↓
２ ３→１ ６ ０ ５ ４┐
↑ │ ↑ │ ↑│
└─────┘ └─┘ └┘
(6,3)*
把 6 拿出來, 它現在是:
┌─┐ ┌─┐
│ ↓ │ ↓ 順著它的 next link 往下走
２ ３→１ ６ 直到走回自己前遇到了 3 !!
↑ │ 所以 isSameGroup(2,1) 就是 ture, ignore (6,3) !
└─────┘
以下略
中間的 link list 處理方法不難, 可以自己想想 :)
--
有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。
存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你
，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也
是比較不容易被擊倒的人。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.56
※ 編輯: ledia 來自: 140.112.30.56 (03/23 13:48)
※ 編輯: ledia 來自: 140.112.30.56 (03/23 13:48)