最近学习到了这两种经典的算法,谈一下自己的理解
深度优先搜索算法(Depth-First-Search,DFS)
广度优先搜索算法(Breadth-First Search,BFS)这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。
通过一个例题就很好理解了:简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。
①深度优先搜索:
假设按照从左向右的顺序,那么V1->V2->V4,节点V4的左边没有节点,向右探索,->V8,到节点V8后没法继续向下探索,因此按照探索顺序回溯,回溯到V2,发现右边有节点,->V5,节点V5没法继续探索,再按照探索顺序回溯,回溯到V1,向右到节点V3,任然遵循从左向右的原则:->V3-V6->V7。
所以结果为:V1->V2->V4->V8->V5->V3-V6->V7
②广度优先搜索:
假设按照从左向右的顺序,那么第一层V1,第二层V2、V3,第三层V4、V5、V6、V7,第四层V8.
所以结果为:V1->V2->V3->V4->V5->V6-V7->V8
可以看到两种方法各有优缺点,这里只是浅谈一下自己的理解,还没有学数据结构,希望多多指正。