存储结构的概念 数据结构图的广度优先遍历算法

在上一篇文章中，我们学习了图的相关存储结构，即邻接矩阵和邻接表。它们分别代表了最典型的两种类型的顺序存储和链式存储。既然数据结构已经有了，那么当然下一步就是学习这些数

在上一篇文章中，我们学习了图的相关存储结构，即邻接矩阵和邻接表。它们分别代表了最典型的两种类型的顺序存储和链式存储。既然数据结构已经有了，那么当然下一步就是学习这些数据结构的操作，也就是算法的部分。无论是图还是树，遍历都是非常重要的一部分。今天，我们先来学习图的两种基本遍历方法。

还记得在树的学习中，我们讲过前序、中序、后序、顺序遍历等几种遍历形式吗？其实首序、中序、末序都可以看作是一种遍历方式。都是用栈结构遍历，特点是先走到黑，再回到未知的路。顺序遍历是用队列逐层遍历，特点是先遍历子节点，然后逐个遍历每个子节点的下一个节点。

复习一下树的遍历方法然后学习图的遍历方法会很简单，因为在图的遍历中，最基础的就是基于栈和队列的两种遍历形式。但是，他们的名字略有不同。基于栈的遍历称为深度优先遍历，基于队列的遍历称为广度优先遍历。其实对应的是树中的首中末顺序遍历和顺序遍历，本质上没有太大区别。

我们还是从栈的遍历开始，也就是图中的深度优先遍历。对于栈，继续推新节点，直到它没有其他子节点，然后返回原来的路由。当一个节点有其他节点时，它将被推送到子节点中。这就是深度遍历的思想。

这里需要注意的是，要记录访问过的节点，当有多个节点有路径连接到某个节点时，要确保这个节点只被访问过一次。这是和树形结构最大的区别，因为树是一路向下的，对等之间没有连接，一个节点只有一个上级节点。该图显示任何节点都可以与任何其他节点相关。

首先，我们来看邻接矩阵深度优先遍历算法的实现。现在看不懂也没关系。拉下来看图，然后一起看。当然，更好的解决办法是自己跑。

$visited = []; // 已访问结点function DFS_AM($graphArr, $x){ global $visited; echo "节点：{$x}", PHP_EOL; $visited[$x] = true; // 当前结点标记为已访问 // y 就是邻接矩阵中的横行 for ($y = 1; $y <= count($graphArr); $y++) { // 循环判断第 [x][y] 个数据是否为 1，也就是是否有边 // 并且这个结点没有被访问过 if ($graphArr[$x][$y] != 0 && !$visited[$y]) { // 进行栈递归，传递的参数是当前这个结点 DFS_AM($graphArr, $y); } }}BuildGraph($graphArr); // 建立邻接矩阵图echo '请输入开始遍历的结点（1-结点数）：'; fscanf(STDIN, "%d", $startNode); // 输入从第几个结点开始访问DFS_AM($graphArr, $startNode); // 开始深度优先遍历

代码量不多吧？这是上一篇文章中用来构建邻接矩阵的代码。如果你已经忘记了，回去看看或者直接从文章底部的链接看源代码。

接下来，我们来测试一下:

# php 5.3图的遍历：深度优先与广度优先.php输入结点数：4请输入边数：3请输入边，格式为 出 入 权：1 2 1请输入边，格式为 出 入 权：1 3 1请输入边，格式为 出 入 权：3 4 1请输入开始遍历的结点（1-结点数）：3节点：3节点：1节点：2节点：4

当然邻接表的遍历思路也是一样的，只不过中间循环算法用的是链特征的方式。

$visited = []; // 已访问结点function DFS_AL($graph, $x){ global $visited; $p = $graph->adjList[$x]; // 指定结点的第一个边结点 echo "节点：{$x}", PHP_EOL; // 输出指定结点的信息 $visited[$x] = true; // 设置该结点已被访问 while($p != null){ $y = $p->adjVex; // 获得边结点信息 if(!$visited[$y]){ // 如果结点没有被访问过 DFS_AL($graph, $y); // 进入这个边结点的深度遍历过程 } $p = $p->nextArc; // 移动到下一个边结点 }}$graph = BuildLinkGraph();$graphBFS = $graph;echo '请输入开始遍历的结点（1-结点数）：';fscanf(STDIN, "%d", $startNode); // 输入从第几个结点开始访问DFS_AL($graph, $startNode);// 开始深度优先遍历

是不是也很简单？下一步是简单地测试它:

# php 5.3图的遍历：深度优先与广度优先.php请输入 结点数 边数：4 3请输入边，格式为 出 入 权：1 2 1请输入边，格式为 出 入 权：1 3 1请输入边，格式为 出 入 权：3 4 1请输入开始遍历的结点（1-结点数）：3节点：3节点：4节点：1节点：2

为什么输出顺序和相邻矩阵不一样？我们上一篇文章实现的邻接表使用的是头插入法，后面输入的数据加在节点链接前面。如果我们把3 4 1作为第一个输入，那么节点的遍历结果和邻接矩阵的遍历结果是一样的。

刚上来看代码，聊了半天算法。你还困惑吗？没关系，我们就看上图吧:

左侧与矩阵相邻，右侧与表相邻。我们测试的图相对简单，有4个节点和3条边。这是一个更复杂的图，有6个节点和5条边。你可以自己测试一下。按照每一步的遍历和执行顺序看小黑圈里的数字。我们先拿邻接矩阵的第一张图来简单说明下一次访问的步骤:

首先我们输入从 结点3 开始访问，然后开始深度遍历，这时输出 结点3第一步 结点3 的循环中获得它和 结点1 有边，于是递归传入 结点1 ，结点1 入栈输出 结点1，目前的递归中 结点1 在栈顶在 结点1 的循环中发现 结点1 和 结点 2 有边，于是递归传入 结点2 ，结点2 入栈输出 结点2，目前的递归中 结点2 在栈顶注意了，重点在这里，结点2 的循环中没有发现与其它未访问的结点有边存在了，于是递归开始返回，也就是开始出栈了，依次返回到 结点1 、结点3，没有任何输出，栈空了，递归回到最外层的函数了继续 结点3 的循环，发现与 结点4 有边，递归传入 结点4输出 结点4，目前的递归中 结点4 在栈顶结点4 的循环中没有发现其它未访问的结点及边了，递归返回，结点4 出栈结点3 循环完成，遍历结束

一步一步说清楚了吧？下面我们自己试着分析一下下面这个复杂图的深度遍历顺序，看看是否和我们程序输出的结果一样。在很多考研或者数据结构考试中，经常会有选择题或者应用题让你手动写出深度优先遍历的顺序！

下一步是广度优先遍历。其实说白了就是我们研究树遍历时的序列遍历。前面说过，深遍历是一条黑的路，没有回头路。广度遍历是一层一层的审查，直到找到出口。

邻接矩阵用于广度优先遍历。核心遍历法其实和深度遍历没什么区别，就是搜索某个节点的边。唯一的区别是递归堆栈被一个队列代替了。

$visited = [];function BFS_AM($graphArr, $x){ global $visited; $queue = InitSqQueue(); // 初始化队列 $graphCount = count($graphArr); // 获取矩阵结点数量 $visited[$x] = true; // 结点标记为已访问 EnSqQueue($queue, $x); // 结点入队 while($x){ // 循环判断结点是否 fasle // 遍历所有结点是否与这个结点有边 for ($y = 1; $y <= $graphCount; $y++) { // 如果有边并且未访问过 if ($graphArr[$x][$y] != 0 && !$visited[$y]) { $visited[$y] = true; // 结点标记为已访问 EnSqQueue($queue, $y); // 结点入队 } } $x = DeSqQueue($queue); // 出队一个结点 echo $x, PHP_EOL; // 输出结点 }}echo '请输入开始广度遍历的结点（1-结点数）：';fscanf(STDIN, "%d", $startNode);BFS_AM($graphArr, $startNode); // 开始广度遍历

代码中的注释也非常清楚。我们直接测试一下:

…………请输入开始广度遍历的结点（1-结点数）：33142

同样，我们也提供了邻接表的链宽优先遍历的核心功能。

$visited = [];function BFS_AL($graph, $x){ global $visited; $visited[$x] = true; // 结点标记为已访问 $queue = InitSqQueue();// 初始化队列 EnSqQueue($queue, $x); // 结点入队 // 如果一直有能出队的结点，就一直循环 // 也就是说，如果队列空了，循环就结束 while(($i = DeSqQueue($queue))!==false){ echo $i, PHP_EOL; // 输出结点 $p = $graph->adjList[$i]; // 结点的第一个边结点 while($p != null){ // 如果不为空 $y = $p->adjVex; // 边结点信息 if(!$visited[$y]){ // 如果没有访问过 $visited[$y] = true; // 标记结点为已访问 EnSqQueue($queue, $y); // 入队结点 } $p = $p->nextArc; // 结点指针指向下一个 } }}echo '请输入开始遍历的结点（1-结点数）：';fscanf(STDIN, "%d", $startNode);BFS_AL($graph, $startNode); // 开始广度遍历

核心循环中的操作其实和深度遍历没有太大区别，也是换成了队列的存储形式。

…………请输入开始广度遍历的结点（1-结点数）：33412

好了，上面列出了算法，接下来就该举例说明了。相信你看一下图就能立刻明白广度优先遍历的具体步骤。

如上图，左边是邻接矩阵，右边是邻接表。这里，我们还是直接一步一步来看左边顶图的遍历操作顺序:

输入 结点3 开始广度遍历，结点标记为已访问，这时 结点3 入队使用 while 循环判断 结点x 是否为 null ，如果不为 null 进入循环体遍历所有结点是否与这个结点有边，如果有边，并且这个结点没有被访问过，标记已访问，加入队列出队一个元素，并赋值给 x输出 x 结点的信息

广度优先遍历没有栈回溯，也就是一个线性队列结束就结束了，所以图会很清晰。对于单个节点，我们会将与之相关的所有节点排队，然后将顶层节点出列，这样就可以像对一棵树的顺序遍历一样，一层一层的遍历整个图。同样，拿起纸笔，找一张更复杂的图片，试着手写一个类似广度优先遍历顺序的标题！