算法--搜索与图

主要内容

DFS

思想

会优先向深处搜索 一旦到达最深处 那么会回溯 但是在回溯的过程中 会边回溯边观察是否有能继续深入的点 如果有 那么继续深入搜 直到他确认该点深处都被搜过了 才会放过这个点 继续回溯

就是按照一颗树的顺序 并且以深度优先的顺序来存放数据

但是我们不需要新建一颗树 而是存放每一次搜索的路径 并且也需要自己写一个栈 系统会有一个隐性栈 帮我们维护栈

同时回溯的时候 要恢复现场 恢复搜索前的现场 如下图

从1 2 _ 回溯时
要恢复到1 _ _ 的样子

BFS

思想

BFS会一层一层查找 他会确保当前层都搜完了 再去搜索下一层

DFS与BFS的比较

DFS空间较小 但是BFS具有最短路性质

之所以DFS没有最短路 如上 加入加一条边 那么要搜索到左下角那个点的话 DFS可能返回的路径是3步 但是最短的是2步 所以不具有最短路性质
但是换做BFS 按层查找 那么肯定会先从最外面那条边搜到目标点

一级目录

二级目录

二级目录

二级目录

一级目录

二级目录

二级目录

二级目录

一级目录

二级目录

二级目录

二级目录