[理工] 算法 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