作者kiwidoit (噗嚕噗嚕)
看板Grad-ProbAsk
標題[理工] 演算法 DFS判斷有無cycle
時間Mon Dec 12 11:43:03 2011
出處為洪逸-演算法-名校攻略裡面的 P.4-14
演算法如下:
ε是屬於的意思XD"
ACYCLIC(G) ----------------->主程式
for each u ε V[G]
begin
color[u] <- WHITE;
end
for each vertex u ε V[G]
begin
if color[u]=WHITE;
begin
then DFS-VISIT(u);
end
end
return False;
----------------------------------------------------->分隔線
DFS-VISIT(u) --------------->副程式
color[u] <- GRAY;
time <- time+1;
d[u] <- time;
for each vεadj[u] <-------請問這個地方是不是應該多加個限制@口@?
begin 不然假設一個只有A,B兩個vertices的圖
if color[v]=WHITE 好像跑起來就會有錯..
begin
DFS-VISIT(v);
end
else if color[v]=GREY
Halt and return True;
end
color[u] <- BLACK;
time <- time+1;
f[u] <- time;
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.22.28
※ 編輯: kiwidoit 來自: 140.123.22.28 (12/12 11:48)
※ 編輯: kiwidoit 來自: 140.123.22.28 (12/12 11:49)
※ 編輯: kiwidoit 來自: 140.123.22.28 (12/12 11:49)
※ 編輯: kiwidoit 來自: 140.123.22.28 (12/12 11:52)
→ Byzantin:沒錯呀，你認為該加什麼限制 12/12 13:29
→ kiwidoit:假設從A開始，現在A的color為GREY，然後FOR迴圈開始找A的 12/12 14:41
→ kiwidoit:鄰居B，因為B的color是WHITE，所以DFS-VISIT(B)，現在B的 12/12 14:43
→ kiwidoit:color跟A一樣都是GREY，然後跑FOR迴圈，找B的鄰居，又找A 12/12 14:44
→ kiwidoit:因為A的color是GREY，所以HALT and return True. 12/12 14:44
→ kiwidoit:可是A跟B應該沒有cycle關西吧= =? 12/12 14:45
→ kiwidoit:麻煩糾正我哪裡有想錯，感謝= =" 12/12 14:48
→ gskman:呃,題目是direct... 12/12 15:23
→ kiwidoit:嗯....=口=!!! ..... 天阿...... 12/12 16:36
→ gskman:常有的事XD,所以每次看不懂的時候就題目多看幾次,當然答案 12/12 16:48
→ gskman:也是有可能會錯的 12/12 16:48
→ kiwidoit:嗯XDD 12/13 09:13