图和深度搜索和广度搜索

一.What-图的概念：如下就是一个图(非线性表数据结构)

1. 图的分类：无向图(微信-不允许单向关注)、有向图(微博-允许单向关注)、带权图(QQ-亲密度)

2. 图相关概念：

• 顶点：图中的元素叫作顶点
• 边：一个顶点可以与任意其他顶点建立连接关系，这种建立的关系叫作边
• 度：跟顶点相连接的边的条数叫做度
• 入度和出度：有向图中把度分为入度(表示有多少条边指向这个顶点)和出度(表示有多少条边是以这个顶点为起点指向其他顶点)
• 带权图：在带权图中每条边都有一个权重

二.图的存储

1. 邻接矩阵

• 邻接矩阵的底层依赖一个二维数组。
• 对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j] 和 A[j][i] 标记为 1；
• 对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，就将 A[i][j] 标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，就将 A[j][i] 标记为 1。
• 对于带权图，数组中就存储相应的权重
• 缺点：浪费存储空间

2. 邻接表存储方法

• 无向图A[i][j] 等于 1，那 A[j][i] 也肯定等于 1，只需要存储一个
• 稀疏图-顶点很多，但每个顶点的边并不多
• 优点：
  存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效方便计算。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算
  存储方式：
• 每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点
• 有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点
• 无向图来说，每个顶点的链表中存储的，是跟这个顶点有边相连的顶点
• 优点：存储节省空间
• 缺点：查找比较耗时间(邻接表中链表的存储方式对缓存不友好，所以比起邻接矩阵，在邻接表中查询两个顶点之间的关系就没那么高效)
• 可以将邻接表中的链表改成平衡二叉查找树(红黑树)等动态数据结构(跳表、散列表等)，这样就可以更加快速地查找两个顶点之间是否存在边了。
• 可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边

3. 逆邻接表：每个顶点的链表中，存储的是指向这个顶点的顶点

思考

1. 如何存储微博、微信等社交网络中的好友关系？支持如下几个操作：
   判断用户 A 是否关注了用户 B；
   判断用户 A 是否是用户 B 的粉丝；
   用户 A 关注用户 B；用户 A 取消关注用户 B；
   根据用户名称的首字母排序，分页获取用户的粉丝列表；
   根据用户名称的首字母排序，分页获取用户的关注列表

2. 如何找出社交网络中的三度好友关系？（可能认识的人）

3. 广度优先搜索（BFS）

4. 深度优先搜索（DFS）

5. 迷宫可以抽象成图，走迷宫可以抽象成搜索算法，你能具体讲讲，如何将迷宫抽象成一个图吗？或者换个说法，如何在计算机中存储一个迷宫？

6. A、IDA等搜索算法