引言:我们如果存储、如何存储微博、微信等社交网络中的好友关系呢
定义
一种非线性数据结构。图中数据我们成为定点(vertex),图中数据的关系我们成为边(edge)。没个定点有多少条边我们成为度(dregee),有向图中,因为关系是有方向的,指向定点的边的数量我们称为入度(in-dregee),指向其他定点的边的数量称为初度(out-degree)如图:
分类
针对图是否有方向我们可分为无向图,和有向图,另外在无向图中我们如果加入类似亲密度的概念还分为带权图
表示方法
临接矩阵存储法
底层用2维数组来表示:
- 无向图:i到j的距离a[i][j]设置为1,a[j][i]也设置为1
- 有向图:i指向j的距离a[i][j]设置为1。如果j指向[i]的距离也设置为1
- 带权图:同无向图是双向关系,只是存储的是权重
如图:
邻接表储存法
上面的方法用来表示关系优点是比较直接,缺点是浪费空间,无向图和带权图下办部分空间几乎都浪费了。我们可以采用之前散列类似的方式来保存图的关系。
key为定点,那么到其他地方的关系我们可以在这个顶点后,他说有的边的关系用一个利于查找的数据结构保存(数组、链表、跳表、红黑树),因为链表的查询复杂度是O(N),我们可以考虑用红黑树查找、删除、添加,O(Log2N),跳表(log2N)来优化他。如图
如何保存用户的关系
对于大量的而用户我们可以用mysql表来存储
- a关注b,写入一条记录a->b状态1,0
- b成为a的粉丝,写入一条记录b->a状态1,1
- 这时候只需要以a或者b把数据加载到内存中,用邻接表方式存储起来即可
1 | CREATE TABLE `social_relation` ( |