DFS和BFS的个人理解

DFS和BFS的个人理解
大概讲解个人理解:
BFS是关于从一个点出发然后走到下一个节点(所有节点都记录)然后对比有无所需要节点,若果没有则进行下一步(重复上面的步骤直到找到所需要的那个节点)
从上面图来表示的话就是用从起点开始先检查ABC是否是所需要的如果不是则换第二梯度DEF因为BC没有下一梯度则认为该分支结束,检查第二梯度有没有合适的如果还是没有则第三梯队。如果上面存在双向的就是F也和B相连接那么F可能会到B但是我们因为判断机制中设置只能从大的往下的走所以不会存在重复的步骤,因此就可以得到最简的数量。
所以我们知道BFS的优缺点是能如果深度不是很高找到最简的步骤很方便,但是消耗内存较大
DFS是表示从一个节点出发一直走到这个节点尾结点,然后回溯到上一个节点,再从上一个节点出发走完这个节点的尾结点(重复上面步骤)
从上面图来说呢就是从起点出发如果走上面那么一定要走到G或者是H或者是F直到走完这个最深的才会停止。
因此我们知道这个DFS算法需要回溯那么他的优缺点就是能找到所有的最优的解,并且不需要那么大的内存(因为可以回溯)所以就会释放内存,而DFS是一直保存着不改变所以占内存较大。

上一篇:BFS与最短路径计算


下一篇:关于图的BFS与DFS算法的总结