深度优先遍历和广度优先遍历

深度优先遍历

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。                                (推荐学习：web前端视频教程）

若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。

若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

说白了深度优先遍历就是一种不撞南墙不会头的算法，他会把一条路走完之后再回溯到有分叉的节点继续遍历。

如图：

广度优先遍历

从图中某个顶点V0出发，并访问此顶点；

从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；

重复步骤2，直到全部顶点都被访问为止。

这是一种层层递进的算法，与树的层序遍历类似。

在广度优先搜索时，会从起点开始“一层一层”扩展的方法来遍历，扩展时每发现一个点就将这个点加入到队列，直到整张图都被遍历过位置。

以上是深度优先遍历和广度优先遍历的详细内容。更多信息请关注PHP中文网其他相关文章！