作者AAQ8 ()
看板Grad-ProbAsk
标题[理工] 演算法 DFS问题
时间Sun Dec 2 16:21:35 2018
https://i.imgur.com/PEtCxd8.jpg
https://i.imgur.com/vDkffoE.jpg
我想问的是详解里用的拓扑排序中的DFS
像是在这个有权重的图作DFS
有规定先追踪权重较小的边吗
如果没有规定的话
那拓扑排序是不是就不一样了
这样会影响到最後的critical path吗
还是最後答案都会一样
感谢各位
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.247.224.24
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1543738898.A.21C.html
1F：推 TEPLUN: 拓墣不考虑权重 顺序不同最後答案也会一样 因为你会有顺 12/03 02:29
2F：→ TEPLUN: 序不一样的情形其实是他们之间没有可比性 所以relax不会影 12/03 02:29
3F：→ TEPLUN: 响彼此 12/03 02:29
4F：推 willier15987: critcal path想成所有可能的拓扑排序後最长的一条就 12/05 14:08
5F：→ willier15987: 可以了 还是有机会有多种解答的吧？ 12/05 14:08