用娱乐的方式说编程
hello 兄弟们
我是浩说
现在的社交软件是层出不穷
什么微信、微博、抖音....
其中的社交达人也成了我们的茶余饭后：
"你关注了谁"
"她有多少粉丝"
"这个网红出事了"
"那个人突然爆火"
就像最近的”张同学“
今天咱们就来研究一下：
如何存储社交软件中的「好友、粉丝关系」
01
好友
我们将每个人用蓝色的圆点表示，而其中的一号就是你，
如果有人和你是"好友"关系，那么就用一条线将对方和你连接起来，就像这样：
这就表示你与2、4、6是好友关系。
接着我们来丰富一下别人的"好友关系"，同样用连线表示：
这样我们就将每个人的"好友"圈子抽象成了圆点、线，
与圆点连线的其它圆点就是我们各自的"好友"圈子。
1 -> 2、4、6
2 -> 1、3、5
这种表现方式就对应着Java的一种数据结构：
图(Graph)
了解了 图 结构我们再来看一下，如何用它来表示"粉丝、关注"关系。
02
粉丝
与"好友"关系不同的是，"粉丝、关注"是一种单向关系，我虽然关注了你，但你不需要同时关注我这个粉丝。
于是我们需要将 图(Graph) 做一个改造，引入"方向"的概念，叫做 有向图：
在理解了 图 之后，这个有向图就很好理解了吧！
那么对于软件后台来说，如何存储"图"这种数据结构呢？
我们可以从以下两个区域来探讨：
内存（如Redis）
硬盘（数据库）
03
"图"的存储
在内存里可以使用这两种方式：
邻接矩阵 Adjacency Matrix
邻接表 Adjacency List
04
邻接矩阵
Adjacency Matrix
这个邻接矩阵其实就是一个二维数组，我们就用上面的图结构来举例子，避免兄弟们忘记所以这里我再放一次：
我们将两个人的编号作为二维数组（Array[x][y]）的下标，若为好友关系，则该坐标位置的值为1，若不是好友，则置为0，
（例：1和2是好友，那么Array[1][2] = 1 ）
于是将这个好友圈子的图(graph)结构转换成邻接矩阵存储之后就是这样的：
05
亲密度
说到这里我们不如再延申一下"好友"关系，经常打游戏的兄弟们应该看到过"亲密度"这个概念，你每次和好友打完游戏都会出现类似的提示：”你和某某的亲密度上升了多少，现在为多少“。
想要表示"亲密度",我们直接保存在邻接矩阵对应的坐标值即可：
使用邻接矩阵的存储方式非常"简单粗暴"，既方便寻找元素又很好理解，
不过缺点也相当明显，就是浪费内存空间，因为若1和2为好友，那么Array[1][2] 为 1 的同时，势必Array[2][1] 也为 1，
所以我们回看上面的邻接矩阵，以红色对角线划分的两部分其实是对称的，也就是说我们只需要一半空间即可，而另一半是完全重复的，相当于浪费了一半的存储空间！
福利"上菜"
800道大厂面试题
1000道基础面试题
同名公众号"浩说编程"，发送数字 "7"
找面试题再也不用东拼西凑
爽到飞起！
06
邻接表
Adjacency List
=邻接表 Adjacency List
邻接表基于数组 + 链表，我们依然用"好友"关系的图来举例
转换为邻接表如下：
邻接表的思路是，在左侧数组中保存每个顶点，每个顶点连接着一条链表用于保存该顶点的所有好友。
以上就是在内存中存储的两种方式。
最后说说硬盘的存储方式吧，对于持久层来说就是单纯的数据库表设计了，最粗暴的方式就是创建一个中间关系表就像这样：
user_id
frend_id
1
2
1
4
1
6
2
3
2
5
3
6
4
5
