作者saladim (殺拉頂)
看板CSSE
標題[問題] 又是看書的問題
時間Sun Jul 24 22:23:03 2011
看書又看到卡住 請大家幫忙解惑阿~~~~
所看的書是 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
1F：推 micklin:看不到圖...preview不給看啊, 不知道你說的地方在哪... 07/25 00:26
2F：→ firejox:短網址... 07/25 00:45
3F：→ firejox:st[w] 的v應該是指的是visit 07/25 00:46
4F：→ firejox:st的意思是state吧 07/25 00:48
書上定義st[w]為node w 的parent是哪個node
※ 編輯: saladim 來自: 114.43.192.170 (07/25 01:44)
5F：推 micklin:可以把全文寫一寫嗎?搞不好書寫錯了.... 07/25 03:42
6F：→ firejox:應該是當走到2-0時v=0 w=2 st[w]=0 07/25 10:35
7F：→ firejox:他那個是以0先出發 07/25 10:35
8F：→ firejox:那段的意思是指v到w的這條邊是屬於DFS tree的其中一條 07/25 10:49
9F：→ firejox:要是w還沒遍歷 以及w的parent是v 才是tree的其中一條邊 07/25 10:56