图（Graph）是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网，地铁网络，朋友关系等等都可以抽象成图结构。图G 是由两个集合 V(G) 和 E(G) 组成的，记为 G=(V,E) ，其中 V(G) 是顶点（vertexes）的非空有限集， E(G) 是边（edges）的有限集合。
图的基本术语
顶点（vertex）：图中的每个节点就是顶点。
边（edge）：图中两个顶点之间的线就叫做边。
路径：路径就是从某个顶点到另一个顶点所要经过的顶点序列。
路径长度：一条路径上经过的边的数量。
回路：一条路径的起点和终点为同一个顶点。
度（Degree）：在无向图中，点的度指与该点相连的边的数量。在有向图中，分为出度和入度，指向该点的边数称为入度；反之，则称为出度。有向图某点度的大小等于该点出度和入度之和。
图的种类比较多，有无向图，有向图，完全图，加权图等，下面我们来看下。
无向图
如果一个图结构中，所有的边都没有方向，那么这种图称为无向图，无向图顶点的边数叫做度。无向图类似于情侣关系，比如在情侣中 A 喜欢 B ，那么 B 也喜欢 A 。由于无向图中的边没有方向，所以在表示边的时候对两个顶点的顺序没有要求，用小括号 (?,?) 表示边。如下图所示 ，顶点 V2 和顶点 V4 之间的边，可以表示为 (V2，V4) ，也可以表示为(V4，V2) 。
对应的顶点集合与边集合如下：
V（G）= {V1，V2，V3，V4，V5}
E（G）= {(V1,V2)，(V1，V3)，(V2，V4)，(V2，V5)，(V3，V4)，(V4，V5)}
有向图
如果一个图结构中，所有的边都有方向，那么这种图称为有向图。有向图类似于单相思，比如 A 喜欢 B ，但 B 不一定喜欢 A 。在有向图中，与一个顶点相关联的边有出边和入边之分。由于有向图的边是有方向的，所以在表示边的时候对两个顶点的顺序就有要求。用尖括号 <?,?> 表示边，如下图所示， <V1，V3> 表示从顶点 V1 到顶点 V3 ，而 <V3，V1> 表示从顶点 V3 到顶点 V1 。
对应的顶点集合与边集合如下：
V（G）= {V1，V2，V3，V4，V5}
E（G）= {<V1，V2>，<V1，V3>，<V2，V4>，<V2，V5>，<V3，V1>，<V3，V4>，<V4，V5>，<V5，V2>}
完全图
在完全图中任意一对顶点之间都有边相连。根据边是否有方向，完全图又可以分为无向完全图与有向完全图，在无向图中如果任意两个顶点之间都存在边，则称该图为无向完全图，同理在有向图中如果任意两个顶点之间都存在方向相反的两条边，则称该图为有向完全图，如下图所示。有向完全图有 n*(n-1) 条边，无向完全图有 n*(n-1)/2 条边。
混合图
在一个图中，边既有有方向，也有无方向的图称作混合图。
稀疏图
边很少的图称为稀疏图。
稠密图
边相对比较多的图称为稠密图。
子图
对于两个图 G=(V,E) 和 G'=(V',E') ，如果 V' 是 V 的子集并且 E' 也是 E 的子集，我们称 G' 是 G 的子图，如下图所示。
简单图
在图中如果任意两顶点之间最多只有一条边（在有向图中为两顶点之间每个方向最多只有一条边），边集中不存在环，这样的图称为简单图，如下图所示，都不属于简单图。
加权图
对图 G 的每一条边 e 来说，都对应于一个值 v ，我们把这个 v 称为 e 的权，把这样的图 G 称为加权图，这个 v 可以表示两点之间的距离，花费时间等。如果每条边没有对应的值，我们称他为非加权图，对于非加权图两点之间如果有边我们用 1 表示，如果没边我们可以用 0 表示，如下图所示。
有向无环图
如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图，如下图所示。
连通图
在无向图中对于每一对顶点 v1 和 v2 有路径相连，则称此图是连通图，如下图所示。
强连通图
在有向图中对于任意一对顶点 v1 和 v2 都存在从 v1 到 v2 和 v1 到 v2 的路径，则称此图是强连通图， n 个顶点的强连通图最多有 n*(n-1) 条边，最少有 n 条边。
弱连通图
把有向图的所有的有向边都替换成无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则原图就是弱连通图。我们可以看到无论是强连通图还是弱连通图都是对于有向图来说的。
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
