在做机试题的时候,什么时候用DFS,什么时候用BFS?
DFS和BFS都是图的遍历的两种形式。
DFS的特点是不具有BFS中按层次顺序遍历的特性,所以DFS不具有最优性。DFS因此常用来求解有没有的问题。DFS所得到的解不一定是最优解。当题目中出现问题是否有解等字眼时,常用DFS来求解。
BFS的特点是按照层次顺序遍历,因此,BFS可以用来求解最优解,当题目中出现最短路径,最少的时间等字眼时,常用BFS来求解。
DFS和BFS都是图的遍历的两种形式。
DFS的特点是不具有BFS中按层次顺序遍历的特性,所以DFS不具有最优性。DFS因此常用来求解有没有的问题。DFS所得到的解不一定是最优解。当题目中出现问题是否有解等字眼时,常用DFS来求解。
BFS的特点是按照层次顺序遍历,因此,BFS可以用来求解最优解,当题目中出现最短路径,最少的时间等字眼时,常用BFS来求解。
相关推荐