图(Graph) 是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V, E)，其中，Ｇ表示一个图，Ｖ是图Ｇ中顶点的集合，Ｅ是图Ｇ中边的集合
各种图定义
无向图：若顶点a 到b之间的边没有方向，则称这条边为无向边，用无序偶对(a,b)来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图
有向图：若从顶点a到b的边有方向，则称这条边为有向边，也称为弧。用有序偶<a,b>来表示，a称为弧尾，b称为弧头。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图
有很少条边或弧的图称为稀疏图，反之称为稠密图
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Ｗeight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)
路径的长度是路径上的边或弧的数目
第一个顶点到最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环
图的抽象数据类型
图的存储结构
邻接矩阵
参考 《大话数据结构第 7 章》
邻接表
参考 《大话数据结构第 7 章》
十字链表
有向图的一种存储方法，本质上是将把邻接表与逆邻接表结合起来
对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢？答案是肯定的，就是把它们整合在一起。这就是有向图的一种存储
方法 : 十字链表
邻接多重表
无向图的一种存储方法，本质上是优化邻接矩阵
小例子
边集数组
最小生成树
构造连通网的最小代价生成树称为最小生成树
- 普里姆算法 (prim)
- 克鲁斯卡尔算法 (kruskal)
最短路径
最短路径指两个顶点之间经过的边上权值之和最少的路径
- 迪杰斯特拉 (Dijkstra) 算法
- 弗洛伊德 (floyd) 算法
