[問題] 又是看書的問題

看板CSSE (電腦科學及軟體工程)作者 (殺拉頂)時間12年前 (2011/07/24 22:23), 編輯推噓2(207)
留言9則, 2人參與, 最新討論串1/2 (看更多)
看書又看到卡住 請大家幫忙解惑阿~~~~ 所看的書是 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

07/25 00:26, , 1F
看不到圖...preview不給看啊, 不知道你說的地方在哪...
07/25 00:26, 1F

07/25 00:45, , 2F
短網址...
07/25 00:45, 2F

07/25 00:46, , 3F
st[w] 的v應該是指的是visit
07/25 00:46, 3F

07/25 00:48, , 4F
st的意思是state吧
07/25 00:48, 4F
書上定義st[w]為node w 的parent是哪個node ※ 編輯: saladim 來自: 114.43.192.170 (07/25 01:44)

07/25 03:42, , 5F
可以把全文寫一寫嗎?搞不好書寫錯了....
07/25 03:42, 5F

07/25 10:35, , 6F
應該是當走到2-0時v=0 w=2 st[w]=0
07/25 10:35, 6F

07/25 10:35, , 7F
他那個是以0先出發
07/25 10:35, 7F

07/25 10:49, , 8F
那段的意思是指v到w的這條邊是屬於DFS tree的其中一條
07/25 10:49, 8F

07/25 10:56, , 9F
要是w還沒遍歷 以及w的parent是v 才是tree的其中一條邊
07/25 10:56, 9F
文章代碼(AID): #1EB2h97c (CSSE)
討論串 (同標題文章)
文章代碼(AID): #1EB2h97c (CSSE)