PHP数据结构-图的遍历：深度优先与广度优先

在之前的文章《PHP数据结构-图的存储结构》中，我们学习完了图的相关的存储结构，也就是 邻接矩阵 和 邻接表 。它们分别就代表了最典型的 顺序存储 和 链式存储 两种类型。既然数据结构有了，那么我们接下来当然就是学习对这些数据结构的操作啦，也就是算法的部分。不管是图还是树，遍历都是很重要的部分，今天我们就先来学习最基础的两种图的遍历方式。

树的遍历演化到图的遍历

还记得在树的学习中，我们讲到过先序、中序、后序以及层序遍历这几种遍历形式吗？其实先序、中序和后序可以看作是一种遍历方式，它们都是使用栈结构来进行遍历，特点就是先一条路走到黑，然后再返回来走没有过的路。而层序遍历则是使用队列一层一层地进行遍历，特点就是先遍历完子结点，然后再挨个遍历每个子结点的下一层结点。

复习完了树的遍历方式再学习图的遍历方式就会非常简单了，因为在图的遍历中，最基础的也是基于栈和队列的两种遍历形式。只不过它们的名字略有不同，基于栈的遍历方式叫作 深度优先遍历 ，而基于队列的遍历方式叫作 广度优先遍历 。其实也就是对应着树中的先、中、后序遍历和层序遍历，本质上没有什么太大的区别。

【