图的遍历:深度优先与广度优先

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

树的遍历演化到图的遍历

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

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


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