php存储图片PHP数据构造图的存储构造

在图的术语中，利用二维数组来表示的图的顺序存储构培养叫做毗邻矩阵。
就像下面这个表格一样。

在这个表格中，我们有横竖两个坐标，X1-4 和 Y1-4 表示这个图中一共有 4 个结点，通过它们的对应关系就可以看做是一个结点与另一个结点之间是否有边。
比如说 X1 和 Y2 这一对坐标 <X1, Y2> ，它们的值是 1 ，这就解释 结点1 到 结点2 之间有一条边。
在这里，我们利用的是无权图，也便是用 0 表示没有边，用 1 表示两个结点之间有边。
同时，它还是一张无向图，以是 <Y2, X1> 的值也是 1 ，它的意图是从 结点2 到 结点1 之间也有一条边。
如果是有向图，那么就要根据有向箭头的指向来确定这条边是否设置为 1 。

上面的这个毗邻矩阵对应的图是什么样子的呢？大家可以自己考试测验手动画一画。
画不出来也不要紧，由于我们才刚开始学嘛。
实在它便是我们最开始展示的那张图的毗邻矩阵。

左边的图便是对应的我们上面的那个表格中的毗邻矩阵。
那么右边那个有向图的毗邻矩阵是什么样子的呢？我们也写写试试。

故意思吧？那么如果是有权图呢？实在很大略的我们将图中的 1 直接换成对应边的权值就可以了，不过有可能有的边的权值便是 0 ，以是在有权图中，我们可以定义一个非常大的数，或者定义一个非常小的负数当做 无限数 来表示这两个结点没有边。

接下来，我们就通过代码来布局这样一个毗邻矩阵的存储构造。
我们还是用无向图的例子来实现。
由于无向图是须要反向的结点也赋值的，以是它比有向图多了一个步骤，其它的基本上都是相似的。

// 毗邻矩阵$graphArr = [];function CreateGraph($Nv, &$graphArr){ $graphArr = []; for ($i = 1; $i <= $Nv; $i++) { for ($j = 1; $j <= $Nv; $j++) { $graphArr[$i][$j] = 0; } }}// 毗邻矩阵function BuildGraph(&$graphArr){ echo '请输入结点数：'; fscanf(STDIN, "%d", $Nv); CreateGraph($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] = $weight; // 如果是无向图，还须要插入逆向的边 $graphArr[$v2][$v1] = $weight; } } }}

在这段代码中，首先我们通过 CreateGraph() 方法来初始化一个二维矩阵。
也便是根据我们输入的结点数量，实现一个 X Y 的二维数组构造，并且定义它的所有值都是 0 ，也便是说，这个图目前还没有边。

然后，在 BuildGraph() 方法调用完 CreateGraph() 之后，我们连续输入边的信息。
先输入边的数量，我们有几条边，如果边小于即是 0 的话就不要连续创建了。
实在还可以严谨一点根据 无向完备图和有向完备图 的定义来让边不能超过最大的限度。

接下来，我们就循环连续输入边的信息，这里我须要的输入格式是边的 出结点 、入结点 、权值。
由于我们的示例是无向图，以是我们除了要为 <x, y> 创建边之外，也要为 <y, x> 创建边。
代码的注释中已经解释了。

阐明代码可能还是比较抽象。
直接运行一下试试吧。

BuildGraph($graphArr);// 请输入结点数：4// 请输入边数：4// 请输入边，格式为 出 入 权：1 2 1// 请输入边，格式为 出 入 权：1 3 1// 请输入边，格式为 出 入 权：1 4 1// 请输入边，格式为 出 入 权：3 4 1print_r($graphArr);// Array// (// [1] => Array// (// [1] => 0// [2] => 1// [3] => 1// [4] => 1// )// [2] => Array// (// [1] => 1// [2] => 0// [3] => 0// [4] => 0// )// [3] => Array// (// [1] => 1// [2] => 0// [3] => 0// [4] => 1// )// [4] => Array// (// [1] => 1// [2] => 0// [3] => 1// [4] => 0// )// )// x//y 0 1 1 1// 1 0 0 0// 1 0 0 1// 1 0 1 0

在命令行环境中调用我们的 PHP 文件，然后根据提示的内容依次输入干系的信息。
末了打印出来的数组内容是不是就和我们上面的表格中千篇一律了。
简大略单的一段代码，我们就实现了图的顺序存储。

可能有的同学会一时懵圈。
由于我第一眼看到的时候也是完备懵了，不过仔细的比拟画出来的图和上面的表格实在立时就能想明白了。
这次我们真的是进入二维的天下了。
是不是觉得图瞬间就把树甩到十万八千里之外了。
完备二叉树的时候，我们的思想是二维的，但构造还是一维的，而到毗邻矩阵的时候，不管是思想还是代码构造，全部都进化到了二维空间，高大上真不是吹的。

说完顺序存储构造，自然不能忽略另一种形式的存储构造，那便是图的链式存储构造。
实在对付图来说，链式构造非常大略和清晰，由于我们只须要知道一个结点和那些结点有边就行了。
那么我们就让这个结点形成一个单链表，一起今后链接就好了，就像下图这样。
（同样以上图无向图为例）

从 结点1 开始，它指向一个后继是 结点2 ，然后连续向后链接 结点3 和 结点4 。
这样，与 结点1 干系的边就都描述完成了。
由于我们展示的依然是无向图的毗邻表表示，以是 结点2 的链表结点指向了 结点 1 。
也便是完成了 <y, x> 的反向指向。

对付代码实现来说，我们可以将头结点，也便是正式的 1-4 结点保存在一个顺序表中。
然后让每个数组元素的值为第一个结点的内容。
这样，我们就可以让链表结点只保存结点名称、权重和下一个结点工具的指向信息就可以了。

// 头结点class AdjList{ public $adjList = []; // 顶点列表 public $Nv = 0; // 结点数 public $Ne = 0; // 边数}// 边结点class ArcNode{ public $adjVex = 0; // 结点 public $nextArc = null; // 链接指向 public $weight = 0; // 权重}

接下来，我们来看看如何利用毗邻表这种构造来建立图。

function BuildLinkGraph(){ fscanf(STDIN, "请输入 结点数 边数：%d %d", $Nv, $Ne); if ($Nv > 1) { // 初始化头结点 $adj = new AdjList(); $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, $weight); // 建立一个结点 $p1 = new ArcNode; $p1->adjVex = $v2; // 结点名称为 入结点 $p1->nextArc = $adj->adjList[$v1]; // 下一跳指向 出结点 的头结点 $p1->weight = $weight; // 设置权重 $adj->adjList[$v1] = $p1; // 让头结点的值即是当前新创建的这个结点 // 无向图须要下面的操作，也便是反向的链表也要建立 $p2 = new ArcNode; // 把稳下面两行与上面代码的差异 $p2->adjVex = $v1; // 这里是入结点 $p2->nextArc = $adj->adjList[$v2]; // 这里是出结点 $p2->weight = $weight; $adj->adjList[$v2] = $p2; } return $adj; } } return null;}

代码中的注释已经写得很清楚了。
可以看出，在毗邻表的操作中，无向图也是一样的比有向图多一步操作的，如果只是建立有向图的话，可以不须要 p2 结点的操作。
特殊须要把稳的便是，在这段代码中，我们利用的是链表操作中的 头插法 。
也便是末了一条数据会插入到 头结点 上，而最早的那个边会在链表的末了。
大家看一下末了建立完成的数据构造的输出就明白了。

print_r(BuildLinkGraph());// AdjList Object// (// [adjList] => Array// (// [1] => ArcNode Object// (// [adjVex] => 4// [nextArc] => ArcNode Object// (// [adjVex] => 3// [nextArc] => ArcNode Object// (// [adjVex] => 2// [nextArc] => // [weight] => 1// )// [weight] => 1// )// [weight] => 1// )// [2] => ArcNode Object// (// [adjVex] => 1// [nextArc] => // [weight] => 1// )// [3] => ArcNode Object// (// [adjVex] => 4// [nextArc] => ArcNode Object// (// [adjVex] => 1// [nextArc] => // [weight] => 1// )// [weight] => 1// )// [4] => ArcNode Object// (// [adjVex] => 3// [nextArc] => ArcNode Object// (// [adjVex] => 1// [nextArc] => // [weight] => 1// )// [weight] => 1// )// )// [Nv] => 4// [Ne] => 4// )

利用毗邻表来建立的图的链式存储构造是不是反而比毗邻矩阵更加的清晰明了一些。
就像树的链式和顺序构造一样，在图中它们的优缺陷也是类似的。
毗邻矩阵占用的物理空间更多，由于它须要两层一样多元素的数组，就像上面的表格一样，须要霸占 4 4 的物理格子。
而毗邻表我们可以直接数它的结点数，只须要 12 个格子就完成了。
而且，更紧张的是，链式的毗邻表可以随时扩展边结点和边数，不须要重新地初始化，我们只须要大略地修正上面的测试代码就能够实现，而毗邻矩阵如果要修正结点数的话，就得要重新初始化全体二维数组了。

对付图来说，除了毗邻矩阵和毗邻表之外，还有其它的一些存储形式，不过都是链式的毗邻表的一些优化和变形而已。
大家有兴趣的可以自己去理解一下 十字链表 、毗邻多重表 这两种存储构造。

好了，根本的存储构造已经铺垫完了，关于图的观点也都熟习节制了，接下来，我们就要准备去做最主要的操作了，那便是如何来对图进行遍历。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5.图/source/5.2图的存储构造.php

参考资料：

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

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

《数据构造高分条记》2020版，天勤考研