深度优先搜索与广度优先搜索

深度优先搜索(DFS)

深度优先搜索使用堆栈数据结构存储树结构,进行遍历,是一种盲目搜索方法,算法图解如下。

需遍历的树如下所示:

深度优先搜索与广度优先搜索

a. 将初始节点S0压栈,如果初始节点是目标节点,则搜索结束;

深度优先搜索与广度优先搜索

b. 寻找与栈顶有邻接关系的节点,存在则按从左到右的顺序将其压栈,不存在则将栈顶数据弹出,该步骤有许多小步骤,具体到本例子,如下:

深度优先搜索与广度优先搜索

c. 执行b步骤时,一旦遍历到目标节点,即结束搜索。

广度优先搜索(BFS)

广度优先搜索与深度优先搜索的区别仅在于广度优先搜索使用队列数据结构存储过程数据,所以具有先进先出的特性,算法流程的差别也仅在于此,因此不重新给出过程图。