图的定义和术语

图是一种比线性表和树形结构更为复杂的数据结构。在线性表中，数据元素之间存在着一对一的关系，即除第一个元素外，每个元素都只有一个前驱；除最后一个元素外，每个元素都只有一个后继。在树形结构中，数据元素之间存在这一对多的关系，即除根节点外，每个节点都只有一个父节点；除叶子节点外，每个节点都有若干个孩子节点。在图状结构中，数据元素之间存在着多对多的关系。

图中的数据元素被称为顶点。设 V 是顶点的有限集，VR 是顶点之间的关系的有限集。

对于 VR 中的任意一个有序偶对 <v, w>，它表示从顶点 v 到顶点 w 的一条弧。v 被称为弧尾或起点，w 被称为弧头或终点。这种图被称为有向图。若对于任意 <v, w> ∈ VR，必有 <w, v> ∈ VR，即 VR 是对称的，则以无序偶对 (v, w) 代替有序偶对 <v, w> 和 <w, v>，它表示 v 和 w 之间的一条边，这种图被称为无向图。

综上所述，图由两部分构成：顶点的集合、边或弧的集合。

设图中顶点的数量为 n、边或弧的数量为 e，则：

• 对于无向图而言，e 的取值范围是 0 到 n × (n - 1) / 2，拥有 n × (n - 1) / 2 条边的无向图被称为完全图
• 对于有向图而言，e的取值范围是 0 到 n × (n - 1)，拥有 n × (n - 1) 条弧的有向图被称为有向完全图

有很少条边或弧的图被称为稀疏图，否则被称为稠密图。

边和弧可以有一个权值，该值表示从一个顶点到另一个顶点的距离或耗费。带权的图被称为网。

对于无向图 G = (V, {E})，若边 (v, w) ∈ E，则称顶点 v 和顶点 w 互为邻接点、v 和 w 相邻接、边 (v, w) 依附于顶点 v、顶点 w、边 (v, w) 和顶点 v、顶点 w 相关联。顶点 v 的度是与 v 相关联的边的数量。

对于有向图 G = (V, {A})，若弧 <v, w> ∈ A，则称顶点 v 关联到顶点 w、顶点 w 关联自顶点 v、弧 <v, w> 与顶点 v、顶点 w 相关联。以顶点 v 为弧尾的弧的数量是 v 的出度；以顶点 v 为弧头的弧的数量是 v 的入度；顶点 v 的度等于 v 的出度加上 v 的入度。在有向图中，弧的数量 = 所有顶点的入度之和 = 所有顶点的出度之和。

从一个顶点到另一个顶点之间的路径是一个顶点序列，如果图是有向图，那么路径也是有向的。路径的长度是路径上边或弧的数量。如果路径的第一个顶点和最后一个顶点相同，那么称该路径为回路或环。如果路径上的所有顶点都不相同，那么称该路径为简单路径。如果路径上的第一个顶点和最后一个顶点相同，其余所有顶点都不相同，那么称该路径为简单回路或简单环。

对于无向图而言，如果任意两个顶点之间都有路径，则称该图为连通图。对于非连通图而言，它的一个极大连通子图被称为一个连通分量。

一个连通图的生成树是一个极小连通子图，它包含所有顶点，但是只包含足以构成一棵树的 n - 1条边。

对于有向图而言，如果任意两个顶点之间都有路径，则称该图为强连通图。有向图的极大强连通子图被称为强连通分量。

如果一个有向图只有一个顶点的入度为 0，其它所有顶点的入度都为 1，则称该图为有向树。一个强连通图的生成森林由若干棵互不相交的有向树组成，这些有向树包含图中所有顶点，但只有足以构成这些有向树的弧。

图的存储结构

1，数组矩阵表示法

用一个数组保存所有顶点，用一个矩阵保存边或弧及其信息（比如权重）

2，邻接表表示法

邻接表表示法是图的一种链式存储结构。它用一个数组保存所有顶点。每个顶点是一个链表，链表的头节点包含两个域：数据域、指向第一个表节点的指针；链表的表节点包含三个域：邻接点在数组中的索引、指向下一个表节点的指针、边或弧的信息（比如权重）

可以看出，对于稀疏图而言，数组矩阵表示法会浪费存储空间。

有向网的 Python 实现，可以参考 tim-chow 的 Github。