图（Graph）是一种非线性结构
图的特点（多对多），顶点之间的关系是任意的，图中任意两个顶点之间都可能相关，顶点的前驱和后继个数无限制。
图：数据元素间存在多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。
图的基本术语
顶点：图中的数据元素。
弧：若 <v, w>∈VR，则 <v, w> 表示从 v 到 w 的一条弧，且称 v 为弧尾，称 w 为弧头，此时的图称为有向图。
G1 = (V1, A1) V1 = {v1, v2, v3, v4}
A1 = {< v1, v2>, < v1, v3>, < v3, v4>, < v4, v1>}
边：若 <v, w>∈VR 必有<w, v>∈VR，则以无序对 (v, w) 代表这两个有序对，表示 v 和 w 之间的一条边，此时的图称为无向图。
G2 = (V2, E2) V2 = {v1, v2, v3, v4, v5}
E2 = {(v1, v2), (v1, v4), (v2, v3), (v2, v5) , (v3, v4), (v3, v5)}
无向图中边的取值范围：0≤e≤n(n-1)/2。（用 n 表示图中顶点数目，用 e 表示边的数目。且不考虑顶点到其自身的边。）
完全图：有 n(n-1)/2 条边的无向图（即：每两个顶点之间都存在着一条边)称为完全图。
有向图中弧的取值范围：0≤e≤n(n-1)。（用 n 表示图中顶点数目，用 e 表示弧的数目。且不考虑顶点到其自身的弧。）
有向完全图：有 n (n - 1) 条弧的有向图（即：每两个顶点之间都存在着方向相反的两条弧）称为有向完全图。
稀疏图：含有很少条边或弧的图。
稠密图：含有很多条边或弧的接近完全图的图。
权：与图的边或弧相关的数，这些数可以表示从一个顶点到另一个顶点的距离或耗费。
网： 带权的图。
子图：如果图 G = (V, E) 和 G´= (V ´, E´)，满足：V ´包含于V 且 E´包含于 E，则称 G´为G 的子图。
邻接点：若 (v, v´) 是一条边，则称顶点 v 和 v´互为邻接点，或称 v 和 v´相邻接；称边 (v, v´) 依附于顶点 v和 v´，或称 (v, v´) 与顶点 v 和 v´ 相关联。若 <v, v´> 是一条弧，则称顶点 v 邻接到 v´，顶点v´邻接自顶点 v。并称弧 <v, v´> 与顶点 v 和 v´ 相关联。
度：无向图中顶点 v 的度是和 v相关联的边的数目，记为：TD(v)。
入度：有向图中以顶点 v 为头的弧的数目称为 v 的入度，记为：ID(v)。
出度：有向图中以顶点 v 为尾的弧的数目称为 v 的出度，记为：OD(v)。
度：入度和出度之和，即：TD(v) = ID(v) + OD(v)。
如果顶点 vi 的度为 TD(vi)，则一个有 n 个顶点 e 条边（弧）的图，满足如下关系：
路径：从顶点 v 到 v´ 的路径是一个顶点序列。对于有向图，路径也是有向的。
路径长度：路径上边或弧的数目。
回路（环）：第一个顶点和最后一个顶点相同的路径。
简单路径：序列中顶点不重复出现的路径。
连通：从顶点 v 到 v´ 有路径，则说 v 和 v´ 是连通的。
连通图：图中任意两个顶点都是连通的。
连通分量：无向图的极大连通子图（该子图是 连通子图，G中再加一个顶点就不连通，再减一条边就不极大）；任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量（非连通图的每一个连通部分）。
强连通图： 任意两个顶点都连通的有向图。
强连通分量：有向图的极大强连通子图（该子图是强连通子图，图中再加一个顶点就不连通，再减一条边就不极大）；任何强连通图的强连通分量只有一个，即其本身；非强连通图有多个强连通分量。
连通图的生成树：包含无向图G 所有顶点的的极小连通子图（该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通；加入一条边，则子图一定有环。 ）一个图可以有许多棵不同的生成树。
2、生成树是图的极小连通子图；
3、一个有 n 个顶点的连通图的生成树有 n-1 条边；
4、生成树中任意两个顶点间的路径是唯一的；
5、在生成树中再加一条边必然形成回路。
6、含 n 个顶点 n-1 条边的图不一定是生成树。
（无向图） 生成森林：由若干棵生成树组成，含有图中全部顶点，但只有足以构成若干棵不相交的生成树的边。
有向树：如果一个有向图恰有一个顶点的入度为 0 ，其余顶点的入度均为 1 ，则是一棵有向树。
有向图的生成森林：由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
图的存储结构
图的存储结构要保存两类信息：
1)顶点的数据
2)顶点间的关系
顺序存储：任意两顶点都可能有联系，不能用元素在存储区中的物理位置来表示元素之间的关系。
多重链表：与树类似，浪费存储单元；操作不方便。
数组表示法（邻接矩阵表示法）
一个有 n 个顶点的图，可用两个数组存储。其中一个一维数组存储数据元素（顶点）的信息，另一个二维数组（邻接矩阵）存储数据元素之间的关系（边或弧）的信息。
邻接矩阵：设 G = (V, VR) 是具有 n 个顶点的图，顶点的顺序依次为 {v1, v2, …, vn}，则 G 的邻接矩阵是具有如下性质的 n 阶方阵：
比如：
使用邻接矩阵存储
再比如
使用邻接矩阵
特点：
1、无向图的邻接矩阵对称，可压缩存储；有 n 个顶点的无向图所需存储空间为 n(n-1)/2。
3、无向图中顶点 vi 的度 TD(vi) 是邻接矩阵中第 i 行 1 的个数。
网的邻接矩阵可定义为：
使用邻接矩阵表示
代码如下：
//图的数组存储表示 #define INFINTY INT_MAX//最大值 #define MAX_VERTEX_NUM 20;//最大的顶点个数 typedef enum{ //有向图 destinationGraphic, //有向网 destinationNet, //无向图 unDestinationGraphic, //无向网 unDestinationNet } GraphKind; typedef struct AreCell{ //顶点的关系类型，对于无权图，用1或者0来表示相邻否，带权图（网）用权值或者无穷大表示相邻否 int adj; //弧（边）相关信息的指针 int *info; } AreCell, AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ //顶点向量 int vexs[MAX_VERTEX_NUM]; //邻接矩阵 AdjMartix arcs; //图的当前顶点数和弧边数 int vexnum, arcnum; //图的种类标志 GraphKind kind; } MGraph;
邻接表（类似于树的孩子链表表示法）
邻接点域，存放与 vi 邻接的顶点在表头数组中的位置。
链域，指示下一条边或弧。
表头结点之后的链表，表示的是该表头的结点代表的图的顶点的邻接的顶点，其中数据域的数字代表的是表头数组的下标，也就是顶点。
读入顶点对<i,j>, 生成两个节点，分别插入顶点j,i的邻接表的头部。直至处理完所有的边。
