[理工] 演算法 DFS問題

看板Grad-ProbAsk作者時間7年前 (2018/12/02 16:21), 編輯推噓2(2推 0噓 3→)
留言5則, 2人參與, 7年前最新討論串1/1
https://i.imgur.com/PEtCxd8.jpg
https://i.imgur.com/vDkffoE.jpg
我想問的是詳解裡用的拓撲排序中的DFS 像是在這個有權重的圖作DFS 有規定先追蹤權重較小的邊嗎 如果沒有規定的話 那拓撲排序是不是就不一樣了 這樣會影響到最後的critical path嗎 還是最後答案都會一樣 感謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.224.24 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543738898.A.21C.html
推
12/03 02:29, 7年前 , 1F
拓墣不考慮權重 順序不同最後答案也會一樣 因為你會有順
12/03 02:29, 1F
→
12/03 02:29, 7年前 , 2F
序不一樣的情形其實是他們之間沒有可比性 所以relax不會影
12/03 02:29, 2F
→
12/03 02:29, 7年前 , 3F
響彼此
12/03 02:29, 3F
推
12/05 14:08, 7年前 , 4F
critcal path想成所有可能的拓撲排序後最長的一條就
12/05 14:08, 4F
→
12/05 14:08, 7年前 , 5F
可以了 還是有機會有多種解答的吧？
12/05 14:08, 5F
‣ 更多 AAQ8 的文章
文章代碼(AID): #1S0vOI8S (Grad-ProbAsk)