作者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
我自己是觉得这样做好像也可以@@"
--
有错请指正<(_ _)>
--
ˋ(′～‵")ˊ
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.121.208.248
1F：推 babyghost:推, 写的真详细. 03/23 15:30
2F：→ babyghost:我以前实作的 code, 参考 DS in C++ 实作版 XD 03/23 15:31
4F：推 cplusplus:一班的UNION用这种做法再加上一点小技巧 可以答到O(1)的 03/24 00:47
5F：→ cplusplus:操作(每种操作 amortised analysis) 03/24 00:48
6F：→ cplusplus:说错 是set的操作 不是union的操作 03/24 00:51