章节1 图的存储方式完全攻略
数据之间的关系有一对一，一对多，多对多，前两种关系可以用链表和树来存储，多对多这种关系需要用到新的数据结构-图来存储
图1 无向图
可以看到v1 与 v3 v4 v2都有关系，v4与v3 v1有关系
图中存储的各个数据元素被称为顶点。如上有v1 v2 v3 v4四个顶点
图2 有向图
图2的各个顶点之间的关系并不是双向的。比如v3 只与v4有关系，v4只与v1存在联系。
图的基本概念
弧头与弧尾 有向图中，无箭头的一端被称为弧尾，箭头的一端称为弧头
入度与出度 箭头指向顶点称为顶点的入度，远离顶点称为顶点的出度 无向图中v1与v2可以表示为(v1, v2)， 有向图中v1 与 v2 的关系可以表示为<v1, v2> 图中存储结构中的顶点之间的关系用线来表示，因此(v1, v2)还可以表示无向图中连接v1 v2的线，又被称作边。图2中<v1, v2>也可以用来表示有向图中从v1到v2带方向的线，又被称为弧。
集合VR 图中习惯用VR来表示图中所有顶点之间关系的集合。例如图1中VR={(v1, v2), (v1, v4), (v1, v3), (v3, v4)},图2 中 VR={<v1, v2>, <v1, v3>, <v3, v4>, <v4, v1>}
路径与回路 无论无向图还是有向图，从一个顶点到另一个顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中的第一个顶点和最后一个顶点相同，则此路径称为回路。
权和网的含义 图中的每条边会赋予一个实数来表示一定的含义，这种与边相匹配的实数称为权，而带权的图通常称为网。
图3 带权的图
图存储接头的分类
根据不同的特征，图可以分为完全图，连通图，稀疏图，稠密图。
完全图：图中的各个顶点都与除自身之外的其他顶点都有关系，这样的无向图称为完全图。同时，满足此条件的有向图则称为有向完全图
具有n个顶点的完全图，图中边的数量为n(n-1)/2；而对于具有n个顶点的有向完全图，图中弧的数量为n(n-1)
稀疏图与稠密图：这两种图是相对存在的，即如果图中具有很少的边，此图称为稀疏图；反之，称为稠密图。
稀疏与稠密的判断条件：e < nlogn，其中e表示图中边的数量，n表示图中顶点的数量。如果式子成立，则为稀疏图；反之称为稠密图