乐趣区

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

jiezi

在上一篇文章中，咱们学习完了图的相干的存储构造，也就是 邻接矩阵 和 邻接表。它们别离就代表了最典型的 顺序存储 和 链式存储 两种类型。既然数据结构有了，那么咱们接下来当然就是学习对这些数据结构的操作啦，也就是算法的局部。不论是图还是树，遍历都是很重要的局部，明天咱们就先来学习最根底的两种图的遍历形式。

树的遍历演变到图的遍历

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

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

深度优先遍历

咱们仍然还是从栈的遍历形式动手，也就是图中的 深度优先遍历 这种模式。对于栈来说，一直地将新的结点压栈，直到发现它没有其它的子结点后再原路返回，当发现某个结点有其它的结点时再进入子结点压栈，这就是深度遍历的思维。

在这里，须要留神的是咱们要记录一下曾经拜访过的结点，当呈现多个结点都有连贯到某一个结点的门路时，保障这个结点只拜访过一次。这是和树结构的最大不同，因为树是一路向下的，平级结点之间没有分割，一个结点只有一个下级结点。而图则是任意一个结点都能够和其它任意的结点有关系。

邻接矩阵

首先，咱们看一下邻接矩阵的深度优先遍历算法的实现。当初看不懂没关系，往下拉去看下图解，而后联合着一起看。当然，更好的计划是本人运行起来。

$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- 结点数）：3
3
1
4
2

邻接表

同样地，咱们也提供邻接表的链式广度优先遍历的外围函数。

$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- 结点数）：3
3
4
1
2

广度优先遍历图示

好吧，下面又列举完了算法，接下来就是图示的工夫了，置信还是一看图大家就马上能明确广度优先遍历的具体步骤了。

和下面的图一样，同样还是右边是邻接矩阵，左边是邻接表。在这里，咱们仍然还是间接分步骤来看一下右边最下面图的遍历操作程序：

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

广度优先遍历没有栈的回溯，就是一条线性的队列走完就完了，所以图示会十分清晰。独自一个结点咱们会将和它相干的所有结点入队，而后出队最顶上的结点，这样就可能像树的层序遍历一样依照一层一层的程序来遍历整个图。同样地，拿起纸笔，找简单一点的图，试试能不能手写出相似于广度优先遍历程序的题目吧！

总结

大家学完了之后是不是发现明天介绍的深度优先和广度优先两种遍历形式真的和树的遍历形式没什么太大的区别。最大的不同就是咱们要标记已拜访过的结点而已。不管怎么说，应用栈和队列来对树或图进行遍历是所有树和图的操作算法中最最根底的局部，也是考试和面试中最常见的问题，大家肯定要深刻了解把握哦！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5. 图 /source/5.3 图的遍历：深度优先与广度优先.php

参考文档：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

各自媒体平台均可搜寻【硬核项目经理】

退出移动版