大家好。
数据结构与算法，这一讲的内容，我们继续第七章图的学习。我们学习图的存储结构。
图，它表达的是节点和节点之间的两两的边的信息。
那因此呢，我们可以很自然地用一个矩阵来表示。
那这个矩阵里面呢，它相应的这个i, j之间的元素
的信息呢就是表示的是这个边是否存在。如果存在呢，
我就把它设为1，不存在就设为0。因此，这个图
的相邻矩阵表达，它所占用的空间呢是0(n²)的，
跟边没有关系。不管它是完全图，
还是稀疏图，都需要花这么多的存储的空间。
那我们来看有向图的这样的一个相邻矩阵的表达。
对应的某一个位置，比如说我们在这个位置，它表达的就是
V3指向V0的这么一个边的信息。
那我们再来看一个带权的无向图。
那对于这样的一个图呢，原来的这样的0,1的有无的信息，我们就
可以把这个1呢这个存在呢，我们表示为它相应的权的值。
那因为它是一个无向图，所以我们从对角线划分开。
那它是一个对称的一个矩阵。
相邻矩阵的实现呢，我们主要是
依赖于一个二维的数组。然后，大家特别要注意一下，
这个边的信息，每一个二维数组里面的
一个元素呢，它代表的是一条边。然后它相应的有
这个边它的起始点、它的终止点，以及权重的信息。
对于稀疏图的情况，这样的一个 相邻矩阵有大量的零元存在。
那我们要找里面的非零元的元素，也就是相应的有效边的时候呢，
我需要逐个的去挨个找。
那是一个这样的双重循环。那会有大量的这样的时间的浪费。
那因为稀疏矩阵它的非零元是很少的，那如果我们能够把这些有效边
给组织起来呢，可能我们的运算也会节省很多。当然它的存储也是 要有很多的节省的。
那我们来看一下我们的一个实现，也就是邻接表的形式。
那邻接表的形式呢，我们是把这个节点组织起来，
然后呢，边呢就跟它关联的这些节点。
我们把这些有效边呢给它串起来。那形成这么一个结构。它同时节省了
空间，而且呢能够提高时间的效率。
那我们看这样的邻接表的信息表达。
那对于节点来说呢，就是这个节点它本身有哪些数据，
还有它所发出来的第一条边的信息。那它的其他的关联边的信息呢，就通过
边的节点，里面它们互相之间指向我的下一个这个
邻接边是什么。当然它们都共有这样的一个起始点的信息。
那我们来看无向图的这样一个邻接表的实现。
那对于这样的一个无向图，它有五条边。那每一条边呢，
它跟两个节点都相关。那会在这个两个节点的
这个边表里面呢出现。那对于这种情况呢，我们特别要注意，尤其是有些运算里面当我
修改一条边的信息的时候，那在无向图的邻接表的实现里面，
我们会要在两个这样的是相应的
边节点里面进行修改。当然这两个边节点，其实它表达的是同一个。因此，我们要
注意信息的一致性。
我们再来看这样一个带权的一个图。
那我们就可以直接地把权重呢作为一个信息域，
放到这个边表里面的这个边节点里面。
对于有向图来说，
我们的邻接表呢常用的就是一个出边表的信息。
也就是说，我从任何一个节点出发，如果我能够
把自己相关联的这些边的信息，也就是说这些边
所涉及到的这些节点的信息，我都能够到的话呢，
那这个信息就是完备的。但是有的时候， 我为了运算操作的方便，我还希望能够表达
这个每一个节点它的入边的信息，
那这样的话呢就是一个逆邻接表，我们也俗称为 入边表。
那图的邻接表的表示呢，它的空间代价
跟节点个数n还有边的个数e是相关的。
对于无向图来说呢，每一条边都被
表达了两次，因此呢是n+2e。
那对于有向图呢，是n+e。当我们这个图很稀疏的时候，
也就是说e呢它会是小于小于n²的。
那我们这样的存储的空间呢是非常节省的，而且呢，
带来了相应的运算的一些效率的提高。
如果我们的出边表
和入边表我们经常会要使用而且经常在一起联合着使用，
那我们就有这么一个十字链的结钩。那可以说是
邻接表和逆邻接表，也就是出边表和入边表的结合。
那我们每一个表目呢，它都会是
有几个域，那也就是它的数据域。
以及它的一个起始点的信息。它的一个终止点的信息。
以及在它的一个出边表里面，它的下一条邻居的信息。
和入边表里面，下一条的邻居的信息。那我们来看，对于这样一个
二维矩阵所表达的一个图的结构。
那我们得到这样的一个出边表的信息，还有
相应的一组这个入边表的信息。那我们可以看到
每一个这样的节点呢，它是由5个域组成的。
也就是说，它的起始点、终结点，它相应的权重，还有
同行的这个下一条边的链，也就是出边链，
然后呢，同一列的下一条边的一个链接，
那也就是入边的这个链接。那数独等等应用里面呢，
我们可以用十字链表来辅助实现。
最后给大家留一下思考题。
对于这种自环的、以及重复边的复杂图结构，
那我们前面介绍的存储结构需要做什么样的修改呢？谢谢大家！