这样是O(|V|)吗?
如果你只是把逆边砍掉的话这样还是O(|V|+|E|)啊
因为你只是把遍历的的时间 sum(deg(v))变成 sum(deg(v))/2
所以原本sum(deg(v)) = 2|E| 而现在是sum(deg(v))/2 = |E|
现在假设有一张4阶完全图
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
从V_1开始跑 花3个时间
然后图变成了这样
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
然后是V_2 花2个时间
图变成
0 0 0 0
0 0 0 0
0 0 0 1
0 0 1 0
然后是V_3 花1个时间
图变成
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
最后是V_4 花0个时间
完成
总共花6个时间 等于图上的边数
我应该没误会Leon大的意思吧?OAO