DFS,BFS算法

粗略的讲一下这两种算法,为老年痴呆做好准备(ノへ ̄、)

DFS:

如上图,你将搜索整张图,而DFS的搜索方法就是,先一味的往前走!走到某个尽头后发现无路可走,后退。咦?后退一步有一个分岔口,这里有多个支路,选择一条没走过的继续走,碰到死胡同,后退,又到了这个分岔口,再去选择没走过的路,直到无路可走,然后返回上一个分岔口。具体过程如下:

                                                       

               

(图中黑色数字均为遍历顺序)

这样一遍历,就把整张图都走过了!不仅如此,起点不论放在哪里,都不会影响遍历整张图的结果。遍历对象也不限于上面的图,还有树,二维,三维矩阵等,总之,DFS思想十分重要。DFS算法适用于解决所有解问题和连通性问题。

BFS

不同于过于鲁莽的DFS,BFS总是优先于身边的各种支路,它一定是先把距离近的优先搜索完,然后逐渐加深层次。如下图的搜索顺序:

                      

(不同颜色代表不同层次,黑色数字亦为搜索顺序)

BFS和DFS大多数时候相同,不同的是,BFS更倾向于解决最短路和最优解问题。其算法的实现依托于队列。(既可手动模拟队列,也可以使用queue)

原文地址:https://www.cnblogs.com/switch-waht/p/11272737.html