DFS(Depth First Search)深度优先搜索

BFS(Breadth First Search)广度优先算法

这是两种最经典的搜索算法 其重要性不言而喻

接下来先讨论一下第一个

DFS

基本思路:

需要一个数组visited[] 来标记已经访问节点

确定开始节点后 如果此节点后继有未访问节点 就访问并标记

对于每一个节点都要判断其后继节点是否访问 从而不断深入

这里用到了递归的思想

接下来用一个案例解释一下这个过程

如图为一个简单的邻接表 初始情况下visted数组初始化为0 表示都未访问

假设我们以顶点3为初始节点 先标记其已访问 再将其输出

接着我们就要判断3的后继节点4 发现其未被访问 输出并标记

由于是深度优先策略 我们在访问4之后 要立即再以4节点为初始节点访问4的后继节点 但发现其第一个后继节点3已被访问 就再访问后一个节点7…… 以此类推 直到所有的顶点都被标记为已经访问结束遍历

核心代码如下

如图为以V0为源点的DFS路径 (其中虚线为回溯路径)