当各边上的权值()时,BFS算法可用来解决单源最短路径问题
A.均相等
B.均互不相等
C.不一定相等
参考答案:A.若所有边的长度相等,广度优先搜索算法是最佳解——亦即它找到的第一个解,距离根节点的边数目一定最少;但对一般的图来说,BFS并不一定回传最佳解。这是因为当图形为加权图(亦即各边长度不同)时,BFS仍然回传从根节点开始,经过边数目最少的解;而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值,BFS的改良算法 成本一致搜寻法 ( en:uniform-cost search )来解决。然而,若非加权图形,则所有边的长度相等,BFS就能找到最近的最佳解。
资源还可以
从浏览器输入URL到展示页面的全流程是怎么样的?
什么是 Cookie?它的作用是什么?
解释一下TCP的滑动窗口。
ArrayList和LinkedList的区别,以及各自是怎么实现扩容的?
资源还可以