Re: 有關Kruskal演算法語法的問題
其實單純要維持集合關係也可以用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
我自己是覺得這樣做好像也可以@@"
--
有錯請指正<(_ _)>
--
ˋ(′～‵")ˊ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.208.248
推
03/23 15:30, , 1F
03/23 15:30, 1F
→
03/23 15:31, , 2F
03/23 15:31, 2F
→
03/23 15:31, , 3F
03/23 15:31, 3F
推
03/24 00:47, , 4F
03/24 00:47, 4F
→
03/24 00:48, , 5F
03/24 00:48, 5F
→
03/24 00:51, , 6F
03/24 00:51, 6F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
