当前课程知识点：数据结构 > 第6章 图 > 6.2 存储与实现 > 讲解（上）
这一节
我们来学习图的存储与实现
先来看第一种实现方式，邻接矩阵，邻接矩阵
是以元素Aij来表示，顶点vi和vj之间的邻接关系
对于一般的图
这里，一般的图
是指边不带权值的图
具体来说
它可能是有向图，也有可能是无向图
我们来看Aij的取值
对于无向图，如果顶点vi、vj之间有一条边，那么Aij的值就是1
对于有向图
如果vi到vj有一条边
那么，Aij的值才是1
对于其他的情况，都是0
也就是说
如果我们用邻接矩阵来存放图
矩阵当中的值要么是1
要么是0
对于带权的图
很明显，不能用1和0，来作为矩阵当中元素的值
我们必须存放边的权值
类似地，如果是无向图
vi、vj之间有一条边
那么，Aij就存放这条边的权值wij
如果是有向图，vi到vj有一条边
我们存放的也是这条边的权值
需要注意
由于我们这里存放的是权值
那么，那些对角线上的元素是多少呢
我们知道，对角线上的元素
i、j值是相等的
也就是说，顶点到自身
我们认为是无穷
换句话说
只有当i不等于j的时候
我们才存放wij
如果i等于j
我们存放的是无穷
当然，有一些资料
可能认为对角线上的元素
它们的值都是0
这也可以
在编程的时候
我们可以将这个无穷，存成某种类型的最大值
或者是取值范围外的某一个值
现在，我们来看具体的例子
我们先给出一个一般的无向图
如果用邻接矩阵来存放，4*4的一个矩阵
因为，有4个顶点
图当中有4条边
对于顶点1，因为顶点1和顶点0、2之间都有边
所以这个矩阵，它的第1行(下标从0开始)和矩阵的第1列
也就是，图当中红色背景和蓝色背景的行和列
你会发现，在这一行或者一列当中
有两个1，这是因为，顶点1和两个顶点之间有边
我们在计算
它的度的时候
1的度
我们既可以扫描一行
也可以扫描一列
因为，这一行、这一列当中，1的个数都是一样的，都是2
在图当中
对角线上的元素都是0
我们去找无向图的邻接矩阵当中，某一个顶点它的度的时候
它的时间复杂度
因为，要扫描矩阵当中的一行或者一列
所以，它的时间复杂度是O(n)
如果我们要找边的数目
对于无向图来说
矩阵当中1的个数，也就是矩阵当中所有元素累加，1的个数是边的数目的两倍
因为，每条边不仅在某一行存了，在某一列
也存了
每条边，实际上对应着两个1
所以，图当中边的数目，应该是矩阵当中所有元素之和，除2
它的时间复杂度
因为，要扫描n^2个元素
所以，是O(n^2)
再来看
一个有向图
有向图
3个顶点，3*3的矩阵
我们看顶点1的入度
找有向图的邻接矩阵中顶点的入度，应该是扫描相应的列
因为
这时候的Aij
它表示的是，vi到vj的这条边，vi到vj
这个入度应该是算在vj上的
这条边对于vi来说，是出度
所以，我们找顶点1的入度，应该去扫描第1列
看它有几个1
只有一个1
所以，它的入度是1
如果你去扫描第1行
有两个1
它的出度是2
时间复杂度，扫描一行或一列
这时候，我们扫描的是列
所以，它的时间复杂度是O(n)，出度是对应的
它扫描的是行
边的数目，图当中
每一条边(每一条弧)，实际上只存了一次
因为，这时候的边是带方向的
所以，图当中边的数目，应该就是矩阵当中1的个数
或者说，是矩阵当中所有元素之和，注意，不用再除2了
它的时间复杂度，也是O(n^2)
我们再来看一个图，这个图
它对应着的邻接矩阵，稍微有点不一样
矩阵的右上区域和左下区域全是0
这是因为，5、6、7这三个顶点
它们和0、1、2、3、4这五个顶点之间，是不可达的
它们之间没有任何的边
右上区域
实际上，就对应着哪些边能到达5、6、7，没有
所以，这个区域是0，左下区域代表的是5、6、7这三个顶点
能到哪些顶点
依然没有
所以，这部分区域也都是0
现在，我们来看一个带权的图
带权的图
我们存放的是权值
而不是1和0
首先，对角线上的元素，都是无穷
刚才我们已经约定了，有一些资料
可能存的是0
其他的情况，我们就看
vi到vj，或者vi和vj之间，是否有边
有边，我们就存放这条边的权值
接下来，我们看邻接矩阵
它的存储
首先
我们定义了一个MaxVertNum
因为，我们用的是顺序存储
我们定义一个最大的容量
然后
定义了一个枚举型的别名
给一个枚举，定义了一个别名
叫GraphKind，图的种类
里面有4个常量
有向图、无向图、有向网和无向网
紧接着
一个结构体
这个结构体的第一个成员，是一个int型
它就代表着
矩阵当中每一个值
对于一般的图，它要么是0
要么是1，对于网
它存放的就是权值，或者是无穷
第二个成员，是描述这条边它的一些信息
所以，我们定义成char型的指针，也就是字符串
这个取决于实际的应用，也可以没有
如果你需要，才用这个字段
比如，有些边
可能描述了一条道路它的描述信息
这时候，边是带有一个字符串的
然后，我们给这样一个结构体
起两个别名，分别叫Edge(边)
第二个别名
是一个二维数组型别名，叫AdjMatrix
也就是我们刚才的邻接矩阵
注意，用这个别名声明变量，声明出来的变量已经是二维数组类型了
第二个结构体，第一个成员，char型的指针
并且是数组
长度
就是我们刚才定义的100
我们用这个成员来存放图当中所有的顶点
注意，顶点是带名称的
也就是字符串
所以，我们用这个成员来存放所有顶点的名称
第二个成员，就是刚才那个结构体的别名
它就是一个二维数组
这个就是刚才的邻接矩阵
紧接着
这两个成员，代表的是图的顶点数和边数
因为，这里的100，仅仅表示一个容量
在100*100的矩阵当中
你表示的图，到底有多少个顶点呢
我们用这个成员来描述
边的数目，用这个成员，第四个成员
GraphKind，我们刚才定义的枚举型别名，用来标识图的类型
然后，给这样一个结构体起个别名，叫AMGraph
也就是Adjacency Matrix Graph，邻接矩阵表示的图
接下来，我们看一个算法
邻接矩阵的创建
我们创建一个邻接矩阵
表示的图G
这里是创建无向网
边带有权值，边没有方向
首先，读入了两个整型的数据
也就是顶点数和边数
开始做循环，循环顶点个数次
每一次，读入一个顶点
它的信息，我们用gets，来接收一个字符串
读入顶点的信息
假设是用来描述一个地图
那么，顶点可能是带有城市的名字的
比如北京
上海
它们是字符串
第二个循环，是一个双重的循环
外层循环循环顶点个数次，内层循环也循环顶点个数次，把邻接矩阵当中每一个值，都赋值成INT_MAX
刚才我们说了
无穷，必须把它转成一个比较大的数
我们这里用的是C
在C语言的limits这个头文件当中
定义了常见的整型
它们的最大值
我们这里
直接用这个头文件当中的INT_MAX
如果是用Java
你可以用Integer这样的包装类里面的静态成员，比如MAX_VALUE
用来表示某一种类型它的最大值
总之
第二个for循环
就是初始化矩阵当中所有的元素为最大值
也就是无穷
第三个for循环，循环边数次
意味着，我们在循环体当中
每次要读入一条边的信息
首先，我们读入这条边是从哪个顶点到哪个顶点
它的权值是多少
因为，我们这里创建的是无向网
边是带有权值的
这里的vi和vj
注意，前面的格式控制串是%s
意味着，vj和vj是顶点的名称
比如，输入的是北京和上海，这两个顶点之间有一条边
紧接着，要去找你输入的这两个顶点名称
在用来表示
顶点的那个一维数组当中
它们的下标是多少
所以，这里有一个函数
当然是伪码，没有实现，叫findVertIndex
去找顶点的下标
在所有顶点构成的一维数组当中，去找名字为vi和vj这两个顶点
它们的下标，找到了之后
然后将
邻接矩阵当中
Aij，也就是edges[i][j]赋值成
你输入的这个权值
然后
输入这条边它的信息
假设你不需要让边带有信息
那么，这个语句你可以不写
别忘了
无向图的邻接矩阵，是一个对称矩阵
这时候，Aij和Aji，都是等于你输入的这个权值的
最后，我们再将图的种类
把它改成UDN
我们刚才定义的
枚举常量，就可以了
这个算法，它的时间复杂度是多少呢
我们只需要看这几个循环
它们的执行次数，就可以了
第一个循环，毫无疑问，执行了n次
第二个循环，是一个双重的循环
内外循环都执行了n次
所以是n^2，第三个循环，循环了边数次
假设边数是e，那么，循环体里面，我们先看这两行语句
这两行语句去扫描一个长度为n的一维数组
所以，它的频度应该是n，有两行
那就是2*n
再加上这四行
所以，这是第三个for循环
它的基本语句执行的次数
最后，我们累加就可以了
在计算时间复杂度的时候
我们把系数、低阶项都去掉
最后是O(n^2+n*e)
因为e的量级
可能是n，也有可能是n^2
我们前面讲完全图的时候
曾经说过，图当中边的数目，最大可以到达n^2这个量级
所以，这个算法的时间复杂度就是O(n^2+n*e)
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
