当前课程知识点：数据结构 > 第7章 图 > 7.2 图的存储结构 > 7.2.1 数组表示法（1）
同学们，大家好
我是云南大学信息学院教师孔兵
这节课我们讨论图的一种存储结构
数组表示法
前面已经讨论了图的逻辑结构
同样需要在计算机中实现图的存储结构
图的任意节点之间都可能有关系，所谓多个前驱
多个后继，因此，图的存储相对于树和线性表
更为复杂
多个前驱，多个后继给我们描述元素之间的关系带来了很大的困难
顺序映象的方式呢，已经不可能了
因为要借助数据元素的存储位置来暗示关系
图中关系的复杂性，使这一点变得不可能实现
非顺序映象，是可行的，但是可能造成空间的浪费
图的第一种存储方式，我们称为数组表示法
这种方法，对于有向图，无向图
甚至有向网和无向网，都可以采用实现其图的存储结构
数组表示法利用两个数组实现图的存储
一个一维数组存储数据元素，也就是顶点的信息
用另外一个二维数组专门来存储数据元素之间的关系信息
也就是边和弧的信息
我们通过例子来具体看一下
从图G1的逻辑结构中，我们可以看到
它包含4个顶点和4条弧
用一维数组，G1.vexs来实现顶点也就是数据元素的存储
4个存储单元0~3分别存储v1到v4
为了描述元素之间的关系，有向图中是弧的信息
用二维数组，G1.arcs实现了关系信息的存储
图中有4个顶点，G1.arcs是一个4×4的二维数组
数组中的一行描述一个顶点的所有后继
行中一个元素描述具体的一条弧
观察二维数组第2行，这行描述的是在G1.vexs中
存储在2号单元这个顶点后继的信息
也就是v3这个顶点后继的信息
第2行第3列红圈中是1，这个1描述的是v3到v4这个有序对
也就是v3到v4红色的这条弧
同理，v1在一维数组0号单元，第0行描述v1的后继
第1列和第2列是1
分别描述了v1有一个后继存在1号单元
是顶点v2，另一个后继存在2号单元
是顶点v3
也就是v1到v2，v1到v3这两条弧
最后一条弧是v4到v1
对应第3行第0列这个1
图中4条弧在二维数组中用4个1描述
从刚才的讨论可以看到
顶点在一维数组中存储的位置对二维数组很重要
顶点存好以后，它和数组下标一一对应
后续处理中，我们一般用顶点的存储位置来代表顶点本身
不过，哪个顶点存在那个单元是任意的
示例中可以看到，G1四个顶点的存储次序是v2,v4,v3,v1
和上一张幻灯的次序不同
不过一旦存好，也就和位置对应了
例如第3行描述的是存储在一维数组第3个单元的顶点v1的后继
第0列的1描述的是存储在3的v1到存储在0的v2之间的弧
v1到v2
第2列的1描述的是v1到v3这条弧
虽然存储的样子不一样
但是，它们同样实现了G1的存储结构
本质是一样的，后续的处理也没有什么不同
数组表示法同样可以存储无向图以图G2为例来说明
仍然是两个数组来实现图的存储
顶点的存储和有向图是一样的
无向路径存储中
关键是边的存储问题
前面我们讨论过，一条边实际上背后是两条弧
那么，在无向图的存储中，一条边被描述为两条弧
以G2中v3到v5这条边为例
这条边背后是v3到v5和v5到v3两条弧
对应地，在二维数组中，是两个红圈当中的两个1
第2行第4列的1，描述v3到v5这条弧
第4行第2列的1，描述从v5到v3这条弧
因为，一条边描述为2条弧
大家可能已经注意到了，这个二维数组是对称的
下面看一下数组表示法存储结构的定义
首先定义一个常量infinity为系统中的最大整数
这是为了存储网，定义最大顶点数为20
这个可以根据需要改变
随后，定义为一个枚举类型
用来描述图的类型，四个值分别表示有向图
有向网，无向图，无向网，给枚举类型取类型名GrahpKing
随后定义一个结构体ArcCell
它是二维数组中一个元素的数据类型
有两个成员，其中adj是一个抽象的关系类型
没有给出具体类型
一般的有向图和无向图中，只需要表示弧的有无
定义为布尔类型就可以了
另一个成员info是一个信息类型的指针
具体问题中，图中的弧
可能有和它相关联的一些其他的信息需要存储
这个要结合具体问题分析，这里只是一个示意
我们后续一般不讨论具体问题
这部分不表示，示意图中也不画出来
二维数组中一般只画出adj这个成员
前面图中就是这样的
Typedef给这个结构体起了一个类型名ArcCell
另外，很重要的，大家注意一下
我们取了一个二维数组类型的名字Adjmatrix
这个是用来存储关系的二维数组的类型名
按前面的定义，它的大小是20×20
它的数据元素类型是结构体ArcCell
最后这个结构体是数组表示法存储结构的定义
结构体有5个成员，第一个成员是一维数组vexs
这是存储顶点的一维数组，大小是最大顶点数
元素类型是数据元素类型
这里是顶点类型，是一回事
第二个成员是二维数组arcs
这是存储顶点关系的二维数组
类型是刚才定义的Adjmatrix
数组的一个元素类型是ArcCell，用来描述关系
两个整型成员vexnum和arcnum表示图中的顶点数
以及边或者弧务的数目
最后一个Grapekind类型的变量kind是
前面定义的枚举类型变量
表示图的类型是4种类型的哪一种
Typedef给这个结构体类型取名Mgraph
这个就是数组表示法的类型名
后面经常会看到，同学们注意一下
同学们，这节课就到这
下次课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
