[問題] Maximum Independent Set(Greedy method)

[cutekid (可愛小孩子)]

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
→ pttworld: 如果有題址我會去衝的。
→ aaaaajack: priority queue
→ aaaaajack: 欸 不對 這樣會跟邊數相關還是n^2
→ aaaaajack: 如果E<<V^2的話就是拔點的時候把鄰居degree-1丟進去
→ aaaaajack: 可以做到O(E log V) 我猜可能可以再壓到O(E)
→ aaaaajack: 要比O(E)再低可能就不是很合理啦 畢竟圖大小就那樣了
→ aaaaajack: 每個degree建個list(vector) 點丟到list裡
→ aaaaajack: 刪點的時候把鄰居degree-1，丟到他該去的list裡
→ aaaaajack: 維護當前最小degree值 刪點頂多-1 所以至多回退V
→ aaaaajack: 每個點只會出現在(移除時degree~原degree)的lsit中
→ aaaaajack: 總數O(E) 所以整體來說應該是O(E)