宽搜和深搜有什么不同

Question

宽搜和深搜分别是用哪个数据结构实现的，用在哪里？

Answer 1

刚好今天作业有道题问了相似问题= =，顺便来回答一下DFS和BFS主要差别在于BFS遍历方式是围绕着根结点一圈一圈（level by level）向外遍历，借助队列的方式实现，而DFS的方式则是从一条路一直走到底后再回退，再走到底，借助栈的方式来实现。在正常情况下二者的时间复杂度都是相同的O（v+e）。一般来说DFS要比BFS好写一些（函数递归调用天然满足栈的结构，并且内存消耗上会比BFS少一些？而BFS只能老老实实用队列）。从宏观上来看：如果你已经知道解离根节点比较近，那么BFS更好如果整体上每个节点的边很多，那么BFS消耗的内存会很大如果一棵树很深而解很少，那么DFS可能会很慢（相反如果解很多并且都比较深的话，那么BFS就会很慢）从名字上就很容易得出，如果一个问题深度无穷而广度有限，那么DFS就没法获得解，但BFS可以，反之也同理。从具体应用上看：DFS比较适合判断图中是否有环，寻找两个节点之间的路径，有向无环图（DAG）的拓扑排序，寻找所有强连通片（SCC），无向图中寻找割点和桥等；BFS则比较适合判断二分图，以及用于实现寻找最小生成树（MST），如在BFS基础上的Kruskal算法。还有寻找最短路径问题（如Dijkstra算法）。