[問題] 又是看書的問題

[saladim (殺拉頂)]

看書又看到卡住 請大家幫忙解惑阿~~~~

所看的書是 Algorithms in C++ by Robert Sedgwick, 第18章的DFS小節(18.4)



裡面提到:

We refer to a link from  v  to  w  in a DFS tree that represents a tree edge
as :
 A tree link if w is unmarked
 A parent link if st[w]  is  v   <----------問題在這點

請參考書上的圖:

http://ppt.cc/Eg@y (抱歉....換成短網址)


我的問題在於 當走到 2-0 這個DFS TREE LINK時(有接到陰影的圓圈那個), 按照我的

理解應該是這樣:

   v = 2 ,  w = 0   st[0] = 0 , 所以2-0不是parent link!!!!

但是這個結論很明顯的錯了.

所以這邊我的疑惑是沒有一個可以自圓其說的方式來決定誰是v 誰是w, 能讓我帶入檢查

的條件裡面, 用以決定某條DFS TREE LINK是那種Link.......

上面舉的例子只是提到parent link, 若是加上其他的link type, v/w的定義又好像

沒有一個一致的定義使的我們可以遵循..............


可以幫忙提示哪邊是思考的重點或是盲點嗎??  這邊想了很久還沒破關.....

感激不盡!!! 謝謝!!!

{若是單獨去想或是用程式去想  都可以做的出來  可是想去想通這套系統.....)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.192.170
推 micklin:看不到圖...preview不給看啊, 不知道你說的地方在哪...
→ firejox:短網址...
→ firejox:st[w] 的v應該是指的是visit
→ firejox:st的意思是state吧
書上定義st[w]為node w 的parent是哪個node
※ 編輯: saladim         來自: 114.43.192.170       (07/25 01:44)
推 micklin:可以把全文寫一寫嗎?搞不好書寫錯了....
→ firejox:應該是當走到2-0時v=0 w=2 st[w]=0
→ firejox:他那個是以0先出發
→ firejox:那段的意思是指v到w的這條邊是屬於DFS tree的其中一條
→ firejox:要是w還沒遍歷 以及w的parent是v 才是tree的其中一條邊