遍历搜索方法

简述

深度优先和广度优先是在图和树的遍历搜索中比较常用的搜索方法

内容

广度优先搜索和深度优先搜索一样，都是对图进行搜索的算法，都是从起点开始顺着边搜索，此时并不知道图的整体结构，直到找到指定节点(即终点)。在此过程中每走到一个节点，就会判断一次它是否为终点；

广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径；

广度优先搜索

广度优先搜索中，有一个保存候补节点的队列，队列的性质就是先进先出，即先进入该队列的候补节点就先进行搜索

上图红色表示当前所在的节点（节点A），终点设为节点G，将与节点A直连的三个节点B, C, D放入存放候补节点的队列中（与节点A直连的三个节点放入时可以没有顺序，这里的放入顺序为B, C, D），用绿色表示；

队列为：[C, D, E, F] ——> [D, E, F, H]——>[E, F, H, I, J]

深度优先搜索

深度优先搜索中，保存候补节点是栈，栈的性质就是先进后出，即最先进入该栈的候补节点就最后进行搜索；

将起点设为节点A，终点设为节点G，还是先将与节点A直连的三个节点B, C, D放入存放候补节点的栈中（这里的放入顺序为D, C, B）

栈为 [D, C, F, K]——>[D, C, F]——> [D, C]——>[D, H]