[理工] 演算法 DFS問題 AAQ8 PTT批踢踢實業坊

[理工] 演算法 DFS問題

作者: AAQ8 (不要就是要) 2018-12-02 16:21:35

https://i.imgur.com/PEtCxd8.jpg
https://i.imgur.com/vDkffoE.jpg
我想問的是詳解裡用的拓撲排序中的DFS
像是在這個有權重的圖作DFS
有規定先追蹤權重較小的邊嗎
如果沒有規定的話
那拓撲排序是不是就不一樣了
這樣會影響到最後的critical path嗎
還是最後答案都會一樣
感謝各位

作者: TEPLUN (mihanami) 2018-12-03 02:29:00

拓墣不考慮權重順序不同最後答案也會一樣因為你會有順序不一樣的情形其實是他們之間沒有可比性所以relax不會影響彼此

作者: willier15987 (Tuantuan) 2018-12-05 14:08:00

critcal path想成所有可能的拓撲排序後最長的一條就可以了還是有機會有多種解答的吧？

繼續閱讀

[理工] 102中央資演ANANquenchan 演算法 P26 程式時間複雜度ENGneweu [理工] 離散2-109AttitudeLA Re: [理工] 線代inner product題目Honor1984 [理工] 線代inner product題目leekevinming [理工] os process觀念題alice85319 [理工] 演算法 maximum flow問題paralyzation [理工] [線代] 內積空間公理證明leekevinming [理工] 離散6-65觀念！Aa841018 [理工] 計組 pipelinedecoder