湖州网站设计,创意办公空间设计案例,网站备案阿里云流程,小程序赚钱的方式文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
1 基本概念
顶点、边 微信#xff1a;A和B是好朋友#xff0c;B也和A是好朋友#xff0c;A和B之间有条边。 入度#xff1a;每个顶点链接的边的个数每个人好朋友…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
1 基本概念
顶点、边 微信A和B是好朋友B也和A是好朋友A和B之间有条边。 入度每个顶点链接的边的个数每个人好朋友的个数。 微博A关注BB不用关注A。从A到B有条边边是有方向的。这样的图是有向图。入度有多条边指向这个节点。出度从这个顶点出发有几条边。 QQ亲密度两个人经常聊天那亲密度高。这就是带权重的边。
2 图的存储方式
2.1 邻接矩阵
用二维数组存储图。 优点表示简单存取速度快便于做矩阵运算。 缺点在无向图中只需要一半的空间即可浪费空间。在稀疏图中节点数量很多每个节点的边的数量却很少造成空间浪费。
2.2 邻接表
邻接表很像一张哈希表。链表的部分可以使用高效的动态数据结构红黑树、跳表、散列表、有序动态数组数据有序排列的动态数组。
3 微信如何存储关系数据
我们先考虑一下微信用户关系我们希望有的操作是 1 判断用户A是否是用户B的好朋友。 2 能够按照首字母排序用户A的好朋友且分页获取。 3 用户A删除用户B为好友同时B的好友列表中也没有。
首先用邻接表存储微信用户关系。因为这是一个稀疏图。微信用户几亿每个人的好友最多也就500。 用户A用户B-用户C-用户X 用户B用户A-用户H-用户Z … 判断用户A是不是用户B的好朋友只需要在用户A的好友列表查找一下即可。好友列表可以用跳表存储。因为跳表可以按照首字母排序。排序好的好友列表也可以提高查询速度。第2个要求满足了。
用户A删除好友用户B需要同时在用户A的好友列表删除B、用户B的好友链表删除A。跳表删除操作时间复杂度O(logn)。
对于数据量小的情况可以存储在内存。当用户量多的时候一台机器就解决不了。可以使用哈希计算将用户好友列表分别存储在不同的服务器。也可以使用外部存储关系型数据库存储数据。
4 BFS and DFS
广度优先搜索BFS和深度优先搜索DFS是最基本的搜索算法。 BFS是以起始点为圆心一层一层由近及远的访问节点形状像波纹。 DFS是以起始点开始一头道走到目的地然后再返回上一层选择另外一条路形状像折线像迷宫。
