作者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