广度优先搜索和深度优先搜索的优缺点（深度与广度优先搜索）



广度优先搜索和深度优先搜索各有他的优点，也有他们的不足之处。
广度优先搜索在遍历的时候不需要全部遍历，搜索到符合条件的就立即终止，这样就不会浪费太多时间。但是在遍历的过程中，他需要创建一个队列来保存遍历的状态（也就是遍历到的每一个结点需要先存入到队列中，然后取出），这样就无非就增加了空间复杂度。
而深度优先搜索则会遍历所有的结点，不需要保存遍历的状态，虽然时间复杂度高但是空间复杂度低。在使用深度优先搜索的时候非常容易超时，因为每次遍历时间复杂度都是以指数的形式增长的。所以我们在使用深度优先搜索的时候我们一般都会联合奇偶剪枝一起使用，这样就极大的降低了深度优先搜索的时间复杂度。
奇偶剪枝：奇偶剪枝就是在你遍历的过程中，首先判断你这个结点能不能按要求到达目的地，如果能，则访问他的邻结点，否则，退出这一层遍历。
部分内容来自：https://blog.csdn.net/chyshnu/article/details/
把矩阵看成如下形式：
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
从为 0 的格子走一步，必然走向为 1 的格子 。
从为 1 的格子走一步，必然走向为 0 的格子 。
即：
从 0 走向 1 必然是奇数步，从 0 走向 0 必然是偶数步。

一般深度优先搜索用来解那种需要得到全部解的题，而广度优先搜索则是用来求最短路径的，到达的每一个结点都是最短路径。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rgzn-sdxx/20079.html