图的概念介绍的差不多了，大家消化一下再继续学习后面的内容。如果没有问题，我们继续学习接下来的内容。当然这还不是最麻烦的部分，因为今天我们只是介绍图的存储结构。图的顺序存储结构：邻接矩阵什么是邻接矩阵首先我们来看一下顺序结构的图是如何存储的。无论是栈、队列还是树，我们都可以用一个简单的数组来实现这些数据结构的顺序存储能力。但是图表是不同的。从上一篇文章我们了解到节点的表示形式是。如果我们把这个节点看成坐标轴上的一个点，是不是可以用一个二维数组来表示呢？没错，让二维数组的第一维表示为x轴，第二维表示为y轴，这样我们就可以建图了。没错，这种形式的二维数组还有一个别名：矩阵。在图学术语中，由二维数组表示的图的顺序存储结构称为邻接矩阵。就像下面的表格。在这个表中，我们有两个坐标，水平和垂直，X1-4和Y1-4表示这个图中有4个节点，它们的对应关系可以看作是一个节点与另一个节点的关系是否有边.例如，X1和Y2的坐标对的值为1，表示节点1和节点2之间有一条边。这里我们使用的是未加权图，即0表示没有边，1表示两个节点之间有边。同时它还是一个无向图，所以的值也是1，它的本意是节点2到节点1也有一条边。如果是有向图，那么需要根据有向箭头的方向判断这条边是否置为1。上面的邻接矩阵对应的图是什么样的呢？你可以尝试手绘。不会画也没关系，因为我们只是在学习。其实就是我们一开始展示的图的邻接矩阵。左图对应上表中的邻接矩阵。那么右边的有向图的邻接矩阵是什么样子的呢？我们也试着写。有趣的？那么如果它是正确的地图呢？其实很简单，我们可以直接用对应边的权值代替图中的1，但是有可能有些边的权值是0，所以在加权图中，我们可以定义一个非常大的数，或者定义一个非常小的负数为无限数，表示两个节点没有边。构造邻接矩阵接下来，我们用代码来构造这样一个邻接矩阵的存储结构。我们还是用无向图的例子来实现。因为无向图需要给反向节点赋值，所以比有向图多了一步，其他基本类似。//邻接矩阵$graphArr=[];functionCreateGraph($Nv,&$graphArr){$graphArr=[];对于($i=1;$i<=$Nv;$i++){对于($j=1;$j<=$Nv;$j++){$graphArr[$i][$j]=0;}}}//邻接矩阵函数BuildGraph(&$graphArr){echo'请输入节点数：';fscanf(STDIN,"%d",$Nv);创建图（$Nv，$graphArr）；if($graphArr){echo'请输入边数：';fscanf(STDIN,"%d",$Ne);if($Ne>0){for($i=1;$i<=$Ne;$i++){echo'请输入边，格式为访问权限：';fscanf(STDIN,"%d%d%d",$v1,$v2,$weight);$graphArr[$v1][$v2]=$权重；//如果是无向图，还需要插入反向边$graphArr[$v2][$v1]=$weight;}}}}在这段代码中，首先我们通过CreateGraph()方法初始化了一个二维矩阵。即根据我们输入的节点个数，实现一个X*Y的二维数组结构，并定义它的所有值都为0，也就是说这个图目前没有边。然后，在BuildGraph()方法调用CreateGraph()之后，我们继续输入边信息。首先输入边数，我们有几个边，如果边数小于等于0，就不要继续创建了。其实也可以严格一点，根据无向完全图和有向完全图的定义，边不能超过最大限制。接下来，我们继续循环输入边缘信息。我这里需要的输入格式是边的出节点，入节点，以及权值。由于我们的示例是一个无向图，因此除了之外，我们还将为创建边。代码的注释中已经说明了。解释代码可能还是比较抽象的。只需运行它并尝试一下。BuildGraph($graphArr);//请输入节点数：4//请输入边数：4//请以访问权限格式输入边数：121//请输入边数访问权限格式：131//请输入边，格式为访问权限：141//请输入边，格式为访问权限：341print_r($graphArr);//数组//(//[1]=>数组//(//[1]=>0//[2]=>1//[3]=>1//[4]=>1//)//[2]=>数组//(//[1]=>1//[2]=>0//[3]=>0//[4]=>0//)//[3]=>数组//(//[1]=>1//[2]=>0//[3]=>0//[4]=>1//)//[4]=>数组//(//[1]=>1//[2]=>0//[3]=>1//[4]=>0//)//)//x//y0111//1000//1001//1010在命令行环境下调用我们的PHP文件，然后根据提示内容依次输入相关信息。最终打印出来的数组内容是不是和我们上面的表格一模一样？通过一段简单的代码，我们就实现了图的顺序存储。有的同学可能一时糊涂了。因为我第一眼看到的时候完全傻眼了，但是仔细对比一下画出来的图和上面的表格，我马上就明白了。这次我们真的进入了二次元世界。是不是感觉画面瞬间把树扔到千里之外？说到完全二叉树，我们的思维是二维的，但结构还是一维的。说到邻接矩阵，无论是思想还是代码结构都进化到了二维空间。图的链式存储结构：邻接表说完顺序存储结构，自然不能忽视另一种形式的存储结构，这就是图的链式存储结构。其实对于图来说，链式结构是非常简单明了的，因为我们只需要知道一个节点与那些节点之间有边即可。然后我们让这个节点组成一个单向链表，一路向后链接，如下图。（同上无向图为例）从节点1开始，指向一个后继节点2，然后继续向后链接节点3和节点4。这样就完成了与节点1相关的边的描述。由于我们仍然展示了无向图的邻接表表示，因此节点2的链表节点指向节点1。即完成了的反方向。对于代码实现，我们可以将头节点，也就是形式上的1-4节点保存在一个序列表中。然后让每个数组元素的值为第一个节点的内容。这样我们就可以让链表节点只保存节点名、权值和下一个节点对象的指向信息。//头节点类AdjList{public$adjList=[];//顶点列表public$Nv=0;//节点号public$Ne=0;//边数}//边节点类ArcNode{public$adjVex=0;//节点public$nextArc=null;//链接指向public$weight=0;//weight}接下来，让我们看看如何使用邻接表结构来构建图。functionBuildLinkGraph(){fscanf(STDIN,"请输入节点数和边数:%d%d",$Nv,$Ne);if($Nv>1){//初始化头节点$adj=newAdjList();$adj->Nv=$Nv;//保存起来方便使用$adj->Ne=$Ne;//保存以便于使用//头节点列表for($i=1;$i<=$Nv;$i++){$adj->adjList[$i]=null;//全部设置为NULL，无边空图}if($Ne>0){//for($i=1;$i<=$Ne;$i++){echo'请输入边，格式为访问权重：';fscanf(STDIN,"%d%d%d",$v1,$v2,$权重);//创建一个节点$p1=newArcNode;$p1->adjVex=$v2;//节点名称为入口节点$p1->nextArc=$adj->adjList[$v1];//下一跳指向出口节点头节点$p1->weight=$weight;//设置权重$adj->adjList[$v1]=$p1;//使头节点的值等于当前新创建的节点//无向图需要进行以下操作，即反向链表也必须建立$p2=newArcNode;//注意下面两行和上面代码的区别$p2->adjVex=$v1;//这里是入口点$p2->nextArc=$adj->adjList[$v2];//这里是退出点$p2->weight=$weight;$adj->adjList[$v2]=$p2;}返回$adj;}}returnnull;}代码中的注释已经写的很清楚了。可以看出，在邻接表的操作中，无向图比有向图多了一步操作，如果只是构建有向图，则不需要p2节点的操作。需要特别注意的是，在这段代码中，我们在链表操作中使用了头部插入的方式。即最后一条数据会被插入到头节点，最早的边会在链表的末尾。我们来看看最终建立的数据结构的输出结果。print_r(BuildLinkGraph());//AdjList对象//(//[adjList]=>Array//(//[1]=>ArcNode对象//(//[adjVex]=>4//[nextArc]=>ArcNode对象//(//[adjVex]=>3//[nextArc]=>ArcNode对象//(//[adjVex]=>2//[nextArc]=>//[weight]=>1//)//[weight]=>1//)//[weight]=>1//)//[2]=>ArcNode对象//(//[adjVex]=>1//[nextArc]=>//[权重]=>1//)//[3]=>ArcNode对象//(//[adjVex]=>4//[nextArc]=>ArcNode对象//(//[adjVex]=>1//[nextArc]=>//[weight]=>1//)//[weight]=>1//)//[4]=>ArcNode对象//(//[adjVex]=>3//[nextArc]=>ArcNode对象//(//[adjVex]=>1//[nextArc]=>//[权重]=>1//)//[权重]=>1//)//)//[Nv]=>4//[Ne]=>4//)使用邻接表构建的图的链式存储结构是否比邻接矩阵更清晰？就像树的链式和顺序结构一样，它们在图中的优缺点是相似的。邻接矩阵占用的物理空间较多，因为它需要两层元素个数相同的数组，就像上面的表格一样，需要占用一个4*4的物理格子。对于邻接表，我们可以直接统计它的节点个数，只需要12个格子就可以完成。而且，更重要的是，链式邻接表可以随时扩展边节点和边的数量，而无需重新初始化。我们只需要简单修改上面的测试代码就可以实现了。如果邻接矩阵需要修改节点数的话，就得重新初始化整个二维数组。小结对于图来说，除了邻接矩阵和邻接表之外，还有其他的存储形式，但都是链式邻接表的优化和变形。有兴趣的可以了解一下交叉链表和邻接多表这两种存储结构。好了，基本的存储结构已经铺好了，图的概念也熟悉了。接下来，我们准备进行最重要的操作，即如何遍历图。测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5。图/source/5.2figure.php的存储结构参考资料：《数据结构》第二版，闫伟民《数据结构》第二版，陈越《数据结构高分笔记》2020年版，天琴考研各自媒体平台可搜索【硬核项目经理】】
