当前课程知识点：数据结构 > 第6章 图 > 6.2 存储与实现 > 讲解（下）
讲完了图的顺序存储之后
我们来看链式存储
也就是这里的邻接表
当图当中的边数，远远小于n(n-1)/2的时候
由于我们采用邻接矩阵
这时候的矩阵，实际上会变成一个稀疏矩阵
比较浪费存储空间
所以，我们用链式存储
我们为每个顶点建立一个单链表
如果一个图包含n个顶点
这个图
就有n个单链表
第i个单链表
它包含所有与vi邻接的边，或者说
对于有向图
就是以vi为弧尾的边
换句话说，就是从vi出来的边
所以，邻接表也称为出边表
对于链表来说
我们都要在链表前面，附设一个头结点
这时候的头结点，实际上就表示顶点
顶点的第一个成员，是顶点自身的信息
可能是北京
上海这样的字符串，第二个成员，是firstEdge
是第一条边
也就是指向从这个顶点出发的第一条边
用来表示边的
结点，是表结点
也就是链表当中后面的结点，都是用来表示边的
它们有三个成员
第一个成员，是这条边
到达哪个顶点
这是对于有向图
如果是无向图
就是它依附的另外一个顶点
第二个成员，是这条边
它的自身信息，可能是一个字符串
如果你存放的是网
那么，这个成员是边的权值
第三个成员，下一条边
它是一个指针，指向下一个表结点
现在，我们来看一个具体的例子
这样一个包含3条边、4个顶点的无向图
因为有4个顶点
所以它有4个链表
每一个链表，头结点表示顶点
第一个成员，是顶点自身的信息
第二个成员，指向第一条边
每一条边包含3个信息
第一个信息，是这条边到达的另外一个顶点，第二个信息
是边自身的信息，是一个字符串
这个图
边没有信息
所以没有存，第三个成员
是下一条边
比如
A、B之间的这条边
它对应的顶点，就是这个顶点
这个顶点，第一个成员的下标是1，对应着的顶点是B
这条边是A、C这条边
我们在邻接表当中，去找顶点的度的时候，很简单
只需要看某一个
链表当中，有多少表示边的表结点，就可以了
对于这个无向图，A这个单链表
它有两个用来表示边的结点
所以，它的度就是2
C只有一个结点
它的度是1，图当中边的数目是多少呢
对于无向图
每一条边，实际上对应着两个表结点
比如
A、B之间的边
这个结点表示了一次
这个结点也表示了一次
所以
邻接表当中
边的数目，应该是所有的表结点数，再除以2
当然
这是对于无向图
我们来看一个有向图
并且边带有权值，4个顶点，4个单链表
每一个
单链表当中，用来表示边的结点
这个值，是一条边到达的那个顶点(的下标)
比如，它是1，它对应着B
那么，这条边就是A到B这条边
也就是这条边
这条边权值是1
所以，中间这个成员存放的权值是1
对于有向图的邻接表
我们找出度
是比较方便的
比如，顶点D
它的出度，我们只需要看这个单链表
当中，有几个表结点就行了
有一个，那么，D结点的出度就是1
因为，邻接表存放的是
从这个顶点出发的边，就是出度
D的入度怎么找呢
这个就麻烦一点了
我们去找D的入度，必须
遍历这4个单链表
看这4个单链表当中的第一个成员
哪些是D的下标
下标
D的下标是2
那么，就看第一个成员
哪些是2
它是一个，它是一个
它是一个，所以，D的入度就是3
因为
表结点当中
第一个成员表示的是，一条边
它到达哪个顶点
也就是以这个顶点
为入度的
所以，D的入度是3
那么，图当中
边的数目是多少呢
就是所有的表结点数
因为是有向图
每条边只表示了一次
现在，我们来看
邻接表的具体实现
我们定义了一个结构体
第一个成员，是一个字符串类型的，用来描述结点的信息
是这个成员，第二成员，是一个指针
指向当前我们正在定义的这个结构体
然后用typedef
起一个别名，叫VertNode
Vertex Node
顶点对应的结点
然后，我们给char型的指针，起了个别名，叫InfoType
这是准备定义表结点的第二个成员
它的类型
第二个结构体，第一个成员
这是
边所到达的那个顶点
它的下标
第二个成员info
如果边的信息是字符串
直接可以用InfoType作为类型
如果边的信息是权值
那这地方，可能要改成int型
第三个成员
是指向下一条边的
所以是指针类型
然后，定义的别名是EdgeNode
边结点
最后一个结构体，第一个成员
是用来表示所有的顶点
构成的一维数组
然后，是图的顶点个数、边的条数
图的种类
我们定义的别名叫ALGraph
也就是Adjacency List Graph，邻接表表示的图
刚才，我们讲邻接表当中，找入度
比较麻烦
需要遍历所有的链表
我们来改进一下
我们现在
就存放以vi为弧头的边
或者说是到达vi的边
即，逆邻接表
它跟刚才的邻接表不一样
我们现在存放以vi为弧头的
或者说到达vi的边，所以，逆邻接表也叫入边表
同样是这个有向网
这是它的逆邻接表
逆邻接表找入度，是比较方便的
我们找D的入度
直接看这个链表
当中有几个表结点，就可以了
3个，D顶点的入度就是3
但是找出度
又比较麻烦
它跟邻接表是对称的
逆邻接表找出度
我们就要去遍历图当中所有的链表
去看这些结点当中
第一个成员，哪些是D的下标2
发现只有一个
这条边表示的是
D到C这条边
所以，D的出度
就是1
图当中
所有的边数，跟邻接表是一样的
就是表结点个数
它代表了图的边数
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
