這樣是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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.8.155
※ 編輯: c2251393 來自: 114.42.8.155 (07/31 18:06)