数据结构与算法-图(graph)

Posted on | Edited on | In ,

引言：我们如果存储、如何存储微博、微信等社交网络中的好友关系呢

定义

一种非线性数据结构。图中数据我们成为定点（vertex），图中数据的关系我们成为边（edge）。没个定点有多少条边我们成为度（dregee），有向图中，因为关系是有方向的，指向定点的边的数量我们称为入度（in-dregee），指向其他定点的边的数量称为初度（out-degree）如图：

avator

分类

针对图是否有方向我们可分为无向图，和有向图，另外在无向图中我们如果加入类似亲密度的概念还分为带权图

表示方法

临接矩阵存储法

底层用2维数组来表示：

  1. 无向图：i到j的距离a[i][j]设置为1，a[j][i]也设置为1
  2. 有向图：i指向j的距离a[i][j]设置为1。如果j指向[i]的距离也设置为1
  3. 带权图：同无向图是双向关系，只是存储的是权重

如图：
avator

邻接表储存法

上面的方法用来表示关系优点是比较直接，缺点是浪费空间，无向图和带权图下办部分空间几乎都浪费了。我们可以采用之前散列类似的方式来保存图的关系。

key为定点，那么到其他地方的关系我们可以在这个顶点后，他说有的边的关系用一个利于查找的数据结构保存（数组、链表、跳表、红黑树），因为链表的查询复杂度是O(N),我们可以考虑用红黑树查找、删除、添加，O(Log2N),跳表（log2N)来优化他。如图

avator

如何保存用户的关系

对于大量的而用户我们可以用mysql表来存储

  1. a关注b,写入一条记录a->b状态1，0
  2. b成为a的粉丝，写入一条记录b->a状态1，1
  3. 这时候只需要以a或者b把数据加载到内存中，用邻接表方式存储起来即可
1
2
3
4
5
6
7
8
9
CREATE TABLE `social_relation` (
  `id` bigint(11) unsigned NOT NULL AUTO_INCREMENT COMMENT 'pk',
  `u_id` char(32) DEFAULT NULL COMMENT '关注u_id',
  `follow_u_id` char(32) DEFAULT NULL COMMENT '被关注u_id',
  `follow_status` smallint(6) DEFAULT NULL COMMENT '关注状态位',
  `followed_status` smallint(11) DEFAULT NULL COMMENT '被关注状态位',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uniq_uid_follow_u_id` (`u_id`,`follow_u_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;