[問題] Maximum Independent Set(Greedy method)
看板Prob_Solve (計算數學 Problem Solving)作者cutekid (可愛小孩子)時間8年前 (2016/10/16 18:02)推噓0(0推 0噓 11→)留言11則, 2人參與討論串1/1
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
→
10/16 20:08, , 1F
10/16 20:08, 1F
→
10/16 20:14, , 2F
10/16 20:14, 2F
→
10/16 20:15, , 3F
10/16 20:15, 3F
→
10/16 20:19, , 4F
10/16 20:19, 4F
→
10/16 20:19, , 5F
10/16 20:19, 5F
→
10/16 20:20, , 6F
10/16 20:20, 6F
→
10/16 20:33, , 7F
10/16 20:33, 7F
→
10/16 20:34, , 8F
10/16 20:34, 8F
→
10/16 20:34, , 9F
10/16 20:34, 9F
→
10/16 20:35, , 10F
10/16 20:35, 10F
→
10/16 20:35, , 11F
10/16 20:35, 11F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
