文章 44
浏览 11238
两种优先搜索

两种优先搜索

深度优先搜索 深度优先搜索采用的是,从首节点出发,一直朝一个方向进行访问相邻节点,直到该方向无相邻节点可以访问为止,这时回到上一节点,从上一节点换一个继续访问,依次重复。直到访问到想要找到的节点,或所有节点全部访问完成。 深度优先搜索的算法模型为: void dfs(int step){ 判断边界 尝试每一种可能 for(i=1;i<n;i++){ 继续下一步dfs(step+i); } 回溯 } 可以看到深度优先搜索,利用的是递归的思想,每次都向深一层访问,直到无法访问。需要注意的是边界条件的判断和尝试吗,每一种可能之后的回溯。 广度优先搜索 广度优先搜索与深度不同,不是采用递归的思路,而是利用了数据结构中的“队列”结构。访问队头元素,将其相邻节点进队,全部相邻元素进栈完成,队头出队。依次重复,直到找到目标节点,或者全部节点被访问完成(也即队列为空)。 深度优先搜索的算法模型为: void dfs(){ while (head<tail){ 判断边界 尝试每一种可能 for(i=1;i<n;i++){ 入队 } 出队队头 } } 以迷宫问题为例 深度优先 vo....