上一篇我们学习了图相关的存储结构，即邻接矩阵和邻接表。它们分别代表了最典型的两种顺序存储和链式存储。既然有了数据结构，那么我们下一步当然是学习这些数据结构的操作，也就是算法的部分。不管是图还是树，遍历都是很重要的一环。今天我们先来学习两种最基本的图遍历方法。树遍历演变成图遍历大家还记得在树的研究中，我们讲过前序、中序、后序、层序遍历的遍历形式吗？其实前序、中序、后序都可以看作是一种遍历方式。它们都使用栈结构进行遍历。层序遍历使用队列逐层遍历。特点是先遍历子节点，再逐个遍历每个子节点的下一级节点。复习完树的遍历方法，学习图的遍历方法就会很简单，因为在图的遍历中，最基本的两种遍历形式是基于栈和队列的。只是他们的名字略有不同。基于栈的遍历方式称为深度优先遍历，基于队列的遍历方式称为广度优先遍历。其实对应的是树中的前、中、后序遍历和层序遍历，本质上没有太大区别。对于深度优先遍历，我们还是从栈遍历的方式入手，也就是图中深度优先遍历的形式。对于栈来说，不断有新的节点入栈，直到发现自己没有其他子节点，然后原路返回。当发现一个节点有其他节点时，就进入子节点，压栈。这就是深度遍历的思想。这里需要注意的是，我们需要记录访问过的节点。当有多个节点有路径连接到某个节点时，确保该节点只被访问过一次。这是与树结构最大的区别，因为树是一路往下走，对等节点之间没有任何联系，一个节点只有一个上级节点。在图中，任何节点都可以与任何其他节点相关。邻接矩阵首先，我们看一下邻接矩阵的深度优先遍历算法的实现。现在看不懂没关系，直接往下拉看图解，再一起看。当然，更好的解决方案是自己运行。$已访问=[];//已访问节点函数DFS_AM($graphArr,$x){global$visited;echo"node:{$x}",PHP_EOL;$已访问[$x]=true；//当前节点被标记为已访问//y是邻接矩阵中的水平行for($y=1;$y<=count($graphArr);$y++){//循环判断是否[x][y]thdatais为1，即是否有边//并且这个节点没有被访问过if($graphArr[$x][$y]!=0&&!$visited[$y]){//栈递归，传递的参数是当前节点DFS_AM($graphArr,$y);}}}BuildGraph($graphArr);//构建邻接矩阵图echo'请输入开始遍历的节点（1-节点数）:';fscanf(STDIN,"%d",$startNode);//输入从哪个节点开始访问DFS_AM($graphArr,$startNode);//开始深度优先遍历代码不多，用上篇文章构建邻接矩阵的代码忘记了，回头看看或者直接从文末链接看源码.接下来，我们将测试：#php5.3图的遍历：深度优先和广度优先。php输入节点号：4请输入边号：3请输入边，格式为访问权：121请输入边，格式为访问权：131请输入边，格式为访问权：341请输入开始遍历的节点（1-节点数）：3节点：3节点：1节点：2节点：4邻接表当然，邻接表遍历的思路是一样的，只是中间的循环算法使用了链特性的方法。$已访问=[];//访问节点函数DFS_AL($graph,$x){global$visited;$p=$graph->adjList[$x];//指定节点的第一个节点点击echo"Node:{$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",$开始节点);//输入要访问的节点数DFS_AL($graph,$startNode);//是否容易开始深度优先遍历，然后简单测试一下：#php5.3图遍历：深度优先广度优先。php请输入节点数和边数：43请输入边，格式为访问权限：121请输入边，格式为访问权限：131请输入边，格式is访问权限：341请输入开始遍历的节点（1-节点数）：3节点：3节点：4节点：1节点：2输出顺序和邻接矩阵是不是相同？上一篇我们实现的邻接表使用的是head插值法，后面输入的数据加在节点链接的前面。如果我们在第一个输入中放入341，那么节点和邻接矩阵的遍历结果是一样的。深度优先遍历图直接上去看代码，然后把算法讲了半天，是不是还一头雾水？没关系，我们直接看上图：左边是邻接矩阵，右边是邻接表。我们测试的图比较简单，4个节点3条边，下面是比较复杂的6个节点5条边的图。你可以自己测试一下。每一步的遍历和执行顺序见小黑圈中的数字。我们先用邻接矩阵的第一张图来简单说明一下访问的步骤：首先我们从节点3进入访问，然后开始深度遍历。此时在第一步的循环中得到输出节点3节点3与节点1有边，因此递归传入节点1，将节点1压入栈中输出节点1。在当前递归，节点1在栈顶节点1的循环中发现节点1和节点1有边，所以递归传入节点2，节点2入栈输出节点2。注意节点2在当前递归中位于堆栈的顶部。这里的关键点是节点2和环路中其他未识别的节点之间没有连接。被访问的节点有边，所以递归开始返回，即开始出栈，依次返回到节点1和节点3。没有输出，栈为空，递归返回最外层函数。继续在节点3的循环中，发现与节点4有一条边，递归传入节点4，输出节点4。在本次递归中，节点4没有找到其他未访问过的节点，就结束了，递归返回，节点4出栈，节点3循环完成，一步一步的遍历结束就很清楚了，下面我们试着分析一下复杂图的深度遍历顺序，看看我们程序输出的结果是不是一样。在很多考研或者数据结构考试中，经常会有选择题或者应用题让你手写深度优先遍历的顺序！广度优先遍历下一步是广度优先遍历。其实说白了就是我们学习树的遍历时的层序遍历。我们之前说过，深度遍历是一条黑路，没有回头路可走。广度遍历就是逐层检查，直到找到出口。邻接矩阵利用邻接矩阵进行广度优先遍历操作。其实核心遍历的方法和深度遍历没什么区别。就是搜索某个节点。唯一的区别是递归堆栈被队列取代了。$visited=[];functionBFS_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=[];functionBFS_AL($graph,$x){global$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'PleaseinputstartNodestraversed(1-numberofnodes):';fscanf(STDIN,"%d",$startNode);BFS_AL($graph,$startNode);//循环中开始广度遍历核心的操作其实和深度遍历没有太大区别，也是换成了队列的存储形式。.........请输入开始广度遍历的节点（1-节点数）：33412，相信大家应该看看图就可以马上明白广度优先遍历的具体步骤了。如上图，左边还是邻接矩阵，右边是邻接表。这里，我们还是直接一步步看左边最上图的遍历操作顺序：输入节点3开始广度遍历，将节点标记为已访问。此时节点3加入队列，使用while循环判断节点x是否为null，如果不为null则进入循环体遍历所有节点是否与该节点有边，如果有边，且该节点没有被访问过，标记为已访问，向队列中添加一个元素，并赋值输出信息广度优先遍历节点x到x，不进行栈回溯，即完成一个线性队列，所以图表会很清晰。对于单个节点，我们会将与其相关的所有节点入队，然后出队最顶层的节点，这样就可以像树的层序遍历一样，逐层遍历整个图。同理，拿起笔和纸，找一张比较复杂的图，试着手写一个类似于广度优先遍历顺序的题目！综上所述，大家学完之后有没有发现，今天介绍的深度优先和广度优先的遍历方法，和树的遍历方法真的没有太大区别。最大的区别是我们必须标记已经访问过的节点。无论如何，使用栈和队列来遍历树或图是所有树和图运算算法中最基础的部分，也是考试和面试中最常见的问题。大家一定要了解和掌握！测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5.Graph/source/5.3图的遍历：depth-firstandbreadth-first.php参考文档：《数据结构》第二版颜伟民《数据结构》第二版陈越《数据结构高分笔记》2020年版天琴考研各媒体平台均可搜索【硬核项目经理】
