[理工] 算法 4-34/44/47

楼主: ff00662299 (goneboy)   2020-09-22 00:43:05
1.
https://imgur.com/uqadjtr
想请问step(3)能不能改BFS找path上weight的最大值。
2.
https://imgur.com/IDA2PYd
https://imgur.com/0kpD0KF
想问一下这题时间复杂度怎么分析,
while内的第一个for大概是从第一个点往外延伸,
但有点不明白第二个for的用意。
3.
https://imgur.com/SKla2n5
https://imgur.com/4NppRXd
想请问这边为什么要用double link list?
感谢解惑!!
作者: A4P8T6X9 (残废的名侦探)   2020-09-22 12:17:00
1, MST 中两个点只有一条路径,用 DFS 还 BFS 一样。2 就是 Dijkstra,第二个循环是找下一个还没碰过的最近点,复杂度为 V^2 + E

Links booklink

Contact Us: admin [ a t ] ucptt.com