图的定义
图是比树更加复杂的非线性表结构。适合存储微博、微信等社交网络中的好友关系。
顶点：图中的元素；用户
边：顶点与任意其它顶点之间的连接关系；好友关系
度：顶点相连接的边的条数；好友个数
有向图：带箭头的边，表示边的方向，有方向的图；关注关系
无向图：边没有方向的图；好友关系
度：无向图中表示一个顶点有多少条边；好友个数
入度：有向图中，表示有多少条边指向这个顶点；粉丝个数
出度：有向图中，表示有多少条边是以这个顶点为起点指向其他顶点；关注人数
带权图：每条边都有一个权重。亲密度
图的存储
邻接矩阵
邻接矩阵-二维数组。
无向图，如果顶点i与顶点j之间有边，就将A[i][j]和A[j][i]标记为1；浪费一半的存储空间；
有向图，如果顶点i到j之间，有一条箭头从顶点i指向顶点j的边，就将A[i][j]标记为1。如果有一条箭头从顶点j指向顶点i的边，就将A[j][i]标记为1。
带权图，数组中就存储相应的权重。
稀疏图，顶点很多，但每个顶点的边不多，邻接矩阵的存储方法更加浪费。优点：
存储方式简单、直接，获取顶点关系高效，图计算-矩阵计算方便。邻接表
邻接表-散列表
无向图每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。
有向图，每个顶点对应的链表里，存储其指向的顶点。优化；
顶点中的链表转换成平衡二叉查找树、红黑树、跳表、散列表、有序动态数组(二分查找)。
应用
微博-有向图
微博操作：- 判断用户A是否关注用户B
- 判断用户A是否被用户B的关注
- 用户A关注用户B
- 用户A取消关注用户B
- 根据用户名称的首字母排序，分页获取用户的粉丝列表
- 根据用户名称的首字母排序，分页获取用户的关注列表
社交关系存储：
- 内存（数据量大用哈希算法将数据分片）
邻接表，存储用户关注了哪些用户；每个顶点的链表中，存储这个顶点指向的顶点。
逆邻接表，存储用户被哪些用户关注；每个顶点的链表中，存储指向这个顶点的顶点。 - 硬盘
两列表。一列用户id，一列关注id。分别建立索引。
微信-无向图
微信操作：- 判断A、B是否为好友关系
- A删除B，断开与B的好友关系
- 展示出A的好友列表，并按名称首字母排序
社交关系存储：
- 邻接表存储每个人对应的好友列表，好友列表可用红黑树/跳表存储