大家好。
数据结构与算法这一讲的内容，我们开始第7章，图的学习。
首先，我们介绍一下图的相关的定义和术语。然后我们介绍它的抽象数据类型。
图，它表示的是顶点和边的
这样的集合。那如果在这个图里面，两两的顶点之间
都有边相关联。那就是形成完全图。
相应于完全图，我们有一种稀疏图。
它很多顶点之间都没有边关联。
那如果是边的条数小于这个完全图的百分之5，我们可以看作它是一种稀疏图。
那还有一种图，它并不是完全图。它也相当的
密集，也就是说它的边的条数，接近于完全图了。那我们
称为密集图。
有一种图它的顶点之间，
的这些边的关联，我们可以看作是无序对。
那也就是说，从v1到v2和从v2到v1，我们没有关系。
那其实它是双向的，也就是说从v1到v2，
有一条边其实隐含着从v2到v1也是相通的，所以我们不画
这个箭头了，就直接画成这样的无向边。那就是无向图。
那有向图，它的这些顶点之间的关联关系的偶对
是有序的。也就是我们从v1到v4有边，但是从
v4到v1不是直接关联的。
那有些情况下，我们这些顶点，
我给它标上号。那在后面，我们引用的时候
就可以引用这个标号来指代相应的这样的结点。在
一些情况下，我们的边它是有权重的。这权重可以代表
从一个结点到另外一个结点，它的开销，例如时间，还是价格等等这些开销。
在图里面，
度是非常重要的一个概念。
那所谓度，就是跟顶点相关联的边的数目。
因为在这样的有向图里面，我们这个关联它是有向的。
那，我们就能看到，从一个顶点出发，它可能发出几条边。那这就是
它的出度。那也可能从一个顶点出发呢，
会有几个边是
指向它自己的。那我们可以看到是它的入度。
还有另一个概念是子图。那对于左边的这样一个图，
我们可以看到，右边就是这个蓝色部分把它提溜出来的
这样的子图。那它的子图里面的所有的顶点，
还有相关的这些边呢，都在原来的图里面要出现。
路径是
图里面一个顶点到另外一个顶点
的这么一些有序的结点边组成的这么一个序链。
在数据结构里面，我们一般讨论的是简单路径，
也就是说在这个序列里面，我们
不允许这些点出现两次。
那，有一个特例就是起点和终点可以重复出现。
那我们看到刚才这样的一个路径，
这些相应的点，我们可以看到，
这两个点，它分别出现了两次。然后这中间，也是
这些点呢，有两次的出现。那这就不是我们的简单路径。
那我们从刚才vp到vq的这个路径的过程中，
它是一个简单路径。那我们看到从刚才从vp到vq的这一条简单路径中，
那它的边的条数就是它的路径长度。
如果这个简单路径中，
它的起始点和终结点是同一个，那就构成了回路。
那如果是一个图，它没有
这样的回路，我们就把它称为无环图。
那有一种特别的，这样的环图，就是有向无环图。我们也称为DAG图。
树和森林，是DAG图的一种特例。
当然还有其它的DAG图。它一般DAG图，
它只要求有向和无环。但是一个顶点，它有
几个这个，指向它的这些边是没关系的，也就是说
这些顶点是可以重入的。而树和森林，我们每一个顶点
它只有一个父结点，也就是说只有一个指向它的边，那就是不允许重入。
我们来观察一下这些回路的情况。那对于3个顶点
这样构成的回路，显然是正确的。那对于两个顶点的情况，
那我们看无向图，这样的两个顶点的情况，我们不认为
它构成了环。实际上，我们对于这种无向图，
它两个顶点之间，我们可以看作它发出了
两条这样的边，是不允许的。这样的在我们数据结构里面
不讨论这样的结构，也就是说在整个数据结构里面，我们都不存在这样的一种图的结构。
在有向图的情况下，这个是一个环。
就是说两个顶点，这两条边，我们是可以构成环的。
还有一种图是有根图，也就是在这个图里面，
有一个顶点，它可以到达其图里面所有的顶点。那这个特殊的顶点就叫做根。
树就是这么一个有根图的情况。那森林呢，
因为它是有若干棵树组成的，所以我们可以说它是有若干棵这样的有根图
组成的，这么一个特殊的图。
如果在无向图里面，
我们从一个点v1到v2有一条路径，那同时，从v2到v1也是
一定有一条路径的。那我们称v1和v2是连通的。
那我们对于无向图的这样的
连通的子图，我们就叫它连通分量。
可以看到这两个子图组成的这个大图，那在左边这个连通分量
里面，它的所有的结点之间，它都是连通的。
那右边这个子图，它们的这个子结点，也是连通的。
那对于有向图，它的
要求就更严格的一些。因为我们从vi到vj
有这样的一个路径的话，也不一定从vj到vi也同样有一条路径。
那如果是这个情况成立，也就是说vi到vj是有路径的，而且
Vj到Vi有路径的，那就称这两个顶点，它是
强连通的。那对于有向图，我们这些
如果是一个子图，它结点内部，它是强连通的。
那我们找出这样的极大的强连通的子图。
那就形成了若干个强连通的分量。
例如我们对于这个大图来说，我们分成了4组
强连通分量。在每一个分量里面，它的
这个结点之间是相通的，但是，分量和分量之间，
它是不构成这样的一个强连通的一个关系。
带权的连通图称为网络。那网络在有些应用里面
也有一些作用。好，那我们看一下图的抽象数据类型。
对于一个数据结构来说，我们最重要的，就是描述它的顶点
以及边的性质。那图的抽象数据类型，我们首先就是要
知道顶点的个数还有边的个数。
另外，因为我们考虑的对于这个图里面每一个顶点。
那它关联到其它的邻居点是什么？那这都是通过边去关联的。那
因此，我们就需要知道有哪一些边。
那为了方便处理，那我们会对这些边来进行这样的标记。
也就是说，我从这个顶点出发，哪一条边是我看到的第一条边，以及下一条边。
那这些边之间，就根据它们出现的先后顺序，那就作为这个发出的
顶点的第一条边以及它们互相知道下一条边是谁。
那这样的话呢，我们就把这一个结点，它的
相应的所有的边都组织起来了。就是我第一条边是谁，
然后下一条边是谁，下一条边的下一条边是谁。
那我们就形成这么一个组织的结构。那在后面呢，我们的存储实现里面可以看到
这样的一个图的，它的发出的边以及这些边之间相应的组织。
另外，对于这么一条边，我需要知道
它的起始点是哪一个，以及它的终止点
是哪一个。还有就是这个边，它的权重是什么。
最后给大家留两个思考。首先呢，就是
对于一个顶点，它是有，我们有从自己
指向自己的一条边，那就是形成一个自环的一个这么一个结构。
另外呢，在两个顶点之间，我们有没有可能
有两条边都是从这个顶点指向另外一个顶点的？
那其实这个现象，在我们的网页里面
是经常出现的。也就是说在一个网页里面，
我可能在某一个点，我会连接到另外一个点。还有就是
两个网页之间，我可能一个网页指向另外一个网页的时候，
它可能有不同的连接入口。但是在数据结构里面，我们只讨论简单的结构，
对着一些复杂的现象，我们会不予考虑。如果你要实现的时候，你可以做些特别的处理。
谢谢大家。