图的定义
图G由顶点集V和边集E组成，记为 G = (V, E)，其中 V(G) 表示图G中顶点的有限非空集；E(G) 表示图G中顶点之间的关系（边）集合。若 V = {v1, v2, … , vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E = {(u, v) | u∈V, v∈V}，用|E|表示图G中边的条数。
注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集。
无向图
若 E 是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为 (v, w) 或 (w, v)，因为 (v, w) = (w, v)，其中 v、w 是顶点。可以说顶点 w 和顶点 v 互为邻接点。边 (v, w) 依附于顶点 w 和 v，或者说边 (v, w) 和顶点 v、w 相关联。
G2 = (V2, E2)
V2 = {A, B, C, D, E}
E2 = {(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)}
有向图
若 E 是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为 <v, w>，其中 v、w 是顶点，v 称为弧尾，w 称为弧头，<v, w> 称为从顶点v到顶点 w 的弧，也称 v 邻接到 w，或w邻接自 v。 <v, w> ≠ <w, v>
简单图
一个图G若满足：①不存在重复边；②不存在顶点到自身的边，则称图G为简单图。
多重图
若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。
顶点的度、入度、出度
**对于无向图：**顶点 v 的度是指依附于该顶点的边的条数，记为 TD(v)。在具有 n 个顶点、e 条边的无向图中：
即无向图的全部顶点的度的和等于边数的 2 倍。
**对于有向图：**入度是以顶点v为终点的有向边的数目，记为 ID(v)；出度是以顶点 v 为起点的有向边的数目，记为 OD(v)。顶点 v 的度等于其入度和出度之和，即 TD(v) = ID(v) + OD(v)。在具有 n 个顶点、e 条边的有向图中：
顶点-顶点的关系描述
**回路：**第一个顶点和最后一个顶点相同的路径称为回路或环。
**简单路径：**在路径序列中，顶点不重复出现的路径称为简单路径。
**简单回路：**除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
**路径长度：**路径上边的数目。
**点到点的距离：**从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
**连通：**无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。
**强连通：**有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。
子图
设有两个图G = (V, E) 和 G` = (V`, E`)，若 V` 是 V 的子集，且 E` 是 E 的子集，则称 G` 是 G 的子图。
若有满足 V(G`) = V(G) 的子图 G`，则称其为 G 的生成子图。
连通分量
无向图中的极大连通子图称为连通分量。
强连通分量
有向图中的极大强连通子图称为有向图的强连通分量。
生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林。
边的权、带权图/网
**边的权：**在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
**带权图/网：**边上带有权值的图称为带权图，也称网。
**带权路径长度：**当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
完全图
**无向完全图：**无向图中任意两个顶点之间都存在边。
**有向完全图：**有向图中任意两个顶点之间都存在方向相反的两条弧。
稀疏图、稠密图
边数很少的图称为稀疏图，反之称为稠密图。
图的存储
邻接矩阵法
邻接矩阵存储是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图片中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
邻接矩阵法存储带权图（网）
邻接表法
当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
所谓邻接表，是指对图G中的每个顶点 v 建立一个单链表，第 i 个单链表中的结点表示依附于顶点 v 的边（对于有向图则是以顶点 vi 为尾的弧），这个单链表就称为顶点 vi 的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点，如图所示。
十字链表
十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。
邻接多重表
邻接多重表是无向图的另一种链式存储结构。
四种存储结构对比：
