图
在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
一个图G = (V, E)由以下元素组成。
V：一组顶点
E：一组边，连接V中的顶点
度的概念
表示一个顶点又多少条边
- 入度 表示又多少条变指向这个顶点
- 出度 表示这个顶点指出多少条边
邻接矩阵
在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。
- 无向图： 顶点 i 和顶点 j 之间有边，就将A[i][j] 和A[j][i] 标记为1
- 有向图 如果 顶点i和顶点 j之间 ，有一条箭头从i指向 j 将A[i][j] 标记为1
- 有权图，数组存储相应的权重
稀疏图
顶点多，但是每个顶点边并不多
应用：微信号几亿的用户，对应到图上就好几亿的顶点，但是每个用户的好友并不会很多，最多5000，如果用邻接矩阵来存储，那么存储空间都被浪费了
邻接表
邻接矩阵存储比较浪费时间，但是使用起来比较节省时间。相反邻接表存储起来比较节省空间，但是使用就比较浪费时间。
上图是否存在一条从顶点2到顶点4的边，就要遍历顶点2对应的链表