Re: [問題] 又是看書的問題

看板CSSE (電腦科學及軟體工程)作者saladim (殺拉頂)時間12年前 (2011/07/26 08:17)推噓0(0推 0噓 3→)

留言3則, 1人參與討論串2/2 (看更多)

※ 引述《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的定義又好像 : 沒有一個一致的定義使的我們可以遵循.............. : 可以幫忙提示哪邊是思考的重點或是盲點嗎?? 這邊想了很久還沒破關..... : 感激不盡!!! 謝謝!!! : {若是單獨去想或是用程式去想都可以做的出來可是想去想通這套系統.....) 回答一下樓友的問題~~~ 基本上我也不知道要打上多少資料上來 XD 最重要的一段就是我貼上來的這段完整的段落需要看書比較好(或是看我貼的link) 我的想像是我沿著DFS TREE LINK走, 所以: 第一步: "0 (V) 走到 2 (W)" 第二步: "2 (V) 走到 0 (W)" 第三步: "0 (V) 走到 2 (W)" .......so on and so forth ........... 出發點就是v 目標點為w, 以這種邏輯下去判斷link是哪種, 在我提的例子裡面就會發生問題.............以上............. 謝謝大家~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.43.192.170