一.What-图的概念：如下就是一个图(非线性表数据结构)
图的分类：无向图(微信-不允许单向关注)、有向图(微博-允许单向关注)、带权图(QQ-亲密度)
图相关概念：
- 顶点：图中的元素叫作顶点
- 边：一个顶点可以与任意其他顶点建立连接关系，这种建立的关系叫作边
- 度：跟顶点相连接的边的条数叫做度
- 入度和出度：有向图中把度分为入度(表示有多少条边指向这个顶点)和出度(表示有多少条边是以这个顶点为起点指向其他顶点)
- 带权图：在带权图中每条边都有一个权重
二.图的存储
- 邻接矩阵
- 邻接矩阵的底层依赖一个二维数组。
- 对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j] 和 A[j][i] 标记为 1；
- 对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，就将 A[i][j] 标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，就将 A[j][i] 标记为 1。
- 对于带权图，数组中就存储相应的权重
- 缺点：浪费存储空间
- 邻接表存储方法
- 无向图A[i][j] 等于 1，那 A[j][i] 也肯定等于 1，只需要存储一个
- 稀疏图-顶点很多，但每个顶点的边并不多
- 优点：
存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效方便计算。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算
存储方式： - 每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点
- 有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点
- 无向图来说，每个顶点的链表中存储的，是跟这个顶点有边相连的顶点
- 优点：存储节省空间
- 缺点：查找比较耗时间(邻接表中链表的存储方式对缓存不友好，所以比起邻接矩阵，在邻接表中查询两个顶点之间的关系就没那么高效)
- 可以将邻接表中的链表改成平衡二叉查找树(红黑树)等动态数据结构(跳表、散列表等)，这样就可以更加快速地查找两个顶点之间是否存在边了。
- 可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边
- 逆邻接表：每个顶点的链表中，存储的是指向这个顶点的顶点
思考
如何存储微博、微信等社交网络中的好友关系？支持如下几个操作：
判断用户 A 是否关注了用户 B；
判断用户 A 是否是用户 B 的粉丝；
用户 A 关注用户 B；用户 A 取消关注用户 B；
根据用户名称的首字母排序，分页获取用户的粉丝列表；
根据用户名称的首字母排序，分页获取用户的关注列表如何找出社交网络中的三度好友关系？（可能认识的人）
广度优先搜索（BFS）
深度优先搜索（DFS）
迷宫可以抽象成图，走迷宫可以抽象成搜索算法，你能具体讲讲，如何将迷宫抽象成一个图吗？或者换个说法，如何在计算机中存储一个迷宫？
A、IDA等搜索算法
