共计 4863 个字符，预计需要花费 13 分钟才能阅读完成。
图的概念介绍得差不多了，大家能够消化消化再持续学习前面的内容。如果没有什么问题的话，咱们就持续学习接下来的内容。当然，这还不是最麻烦的中央，因为明天咱们只是介绍图的存储构造而已。
图的顺序存储构造：邻接矩阵
什么是邻接矩阵
首先还是来看看如何用程序构造来存储图。不论是栈、队列、树，咱们都能够应用一个简略的数组就能够实现这些数据结构的顺序存储能力。然而图就不一样了，从上篇文章中，咱们学到过，一个结点的示意是 <x, y> 这种模式。如果咱们把这个结点相像是一个坐标轴上的点，那么咱们是不是就能够用一个二维数组来示意它呢？没错，让二维数组的第一维示意为 x 轴，第二维示意为 y 轴，这样咱们就能够构建出一张图来了。没错，二维数组这种模式还有一个别名就叫做：矩阵。
在图的术语中，应用二维数组来示意的图的顺序存储构造就叫做邻接矩阵。就像上面这个表格一样。
在这个表格中，咱们有横竖两个坐标，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 1
print_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 版，天勤考研
各自媒体平台均可搜寻【硬核项目经理】