作者cutekid (可愛小孩子)
看板Prob_Solve
標題[問題] Maximum Independent Set(Greedy method)
時間Sun Oct 16 18:02:39 2016
Maximum Independent Set Greedy Method 如下:
Greedy(G):
S = {}
While G is not empty:
Let v be a node with minimum degree in G // 選擁有最小 degree 的點
S = union(S, {v})
remove v and its neighbors from G // 將選到的點和它的鄰居刪掉
return S
------------------
想問每次做完 remove 的動作之後
因為每個點的 degree 會有所變動
怎樣可以快速找到下一個擁有「最小 degree 的點」呢
最直覺的是每次重新 for loop scan 一次找最小 degree 的點
這樣整個算法在查找最小 degree 的點的複雜度是 O(V ^ 2)
有更好的算法嗎
謝謝 ^__^
※ 編輯: cutekid (61.221.80.36), 10/16/2016 18:06:44
1F：→ pttworld: 如果有題址我會去衝的。 10/16 20:08
2F：→ aaaaajack: priority queue 10/16 20:14
3F：→ aaaaajack: 欸 不對 這樣會跟邊數相關還是n^2 10/16 20:15
4F：→ aaaaajack: 如果E<<V^2的話就是拔點的時候把鄰居degree-1丟進去 10/16 20:19
5F：→ aaaaajack: 可以做到O(E log V) 我猜可能可以再壓到O(E) 10/16 20:19
6F：→ aaaaajack: 要比O(E)再低可能就不是很合理啦 畢竟圖大小就那樣了 10/16 20:20
7F：→ aaaaajack: 每個degree建個list(vector) 點丟到list裡 10/16 20:33
8F：→ aaaaajack: 刪點的時候把鄰居degree-1，丟到他該去的list裡 10/16 20:34
9F：→ aaaaajack: 維護當前最小degree值 刪點頂多-1 所以至多回退V 10/16 20:34
10F：→ aaaaajack: 每個點只會出現在(移除時degree~原degree)的lsit中 10/16 20:35
11F：→ aaaaajack: 總數O(E) 所以整體來說應該是O(E) 10/16 20:35