后浪笔记一零二四

图的存储

图中的元素我们就叫做顶点（vertex），图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边（edge）。

边有方向的图叫做“有向图”，边没有方向的图就叫做“无向图”，每条边都带有权重的图叫做“带权图”。

  • 无向图：
    • 跟顶点相连接的边的条数，叫做顶点的度（degree）。
    • 微信好友的双向关注
  • 有向图：
    • 分为入度（In-degree）和出度（Out-degree）
      • 顶点的入度，表示有多少条边指向这个顶点；
      • 顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。
    • 微博好友的单向关注
  • 带权图：
    • 我们可以通过这个权重来表示 QQ 好友间的亲密度。

邻接表

(1)---->(2)---->(3)       [1]{ }->[2]{/}
 ^    > |     >           [2]{ }->[3]{ }->[5]{ }->[4]{/}
 |  <   v    /            [3]{/}
(4)<----(5)               [4]{ }->[1]{ }->[2]{/}
                          [5]{ }->[4]{ }->[3]{/}

每个顶点对应一条链表，

  • 无向图：链表中存储的是与这个顶点有边相连的顶点。
  • 有向图：链表中存储的是这个顶点指向的顶点。

邻接表存储起来比较节省空间，但是使用起来就比较耗时间。

  • 如果我们要确定，是否存在一条从顶点 2 到顶点 4 的边，那我们就要遍历顶点 2 对应的那条链表，看链表中是否存在顶点 4。
  • 链表的存储方式对CPU缓存不友好。
  • 实际开发中，可以将邻接表中的链表改成平衡二叉查找树

用一个邻接表来存储这种有向图是不够的，还需要一个逆邻接表

  • 邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。
    • 邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点，
    • 逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点

数据规模

  • 如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，我们可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。
  • 如果对于大规模的数据，比如微博那样有上亿的用户，数据规模太大，我们就无法全部存储在内存中了。

    • 通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。

    • 利用数据库来存储关系数据

      1. 需求：A、B两个用户，如果相互关注，则成为好友。
      2. 设计上是有两张表，一个是like表，一个是friend表，like表有user_id、liker_id两个字段， 我设置为复合唯一索引即uk_user_id_liker_id。语句执行逻辑是这样的：
      # 以A关注B为例：
第一步，先查询对方有没有关注自己（B有没有关注A）
select * from like where user_id = B and liker_id = A;

如果有，则成为朋友
insert into friend;

没有，则只是单向关注关系
insert into like;

      但是如果A、B同时关注对方，会出现不会成为好友的情况。因为上面第一步，双方都没关注对方。 第一步即使使用了排他锁也不行，因为记录不存在，行锁无法生效。请问这种情况，在MySQL锁 层面有没有办法解决。

      1. 在MySQL上模拟
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

      CREATE TABLE `like` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`user_id` int(11) NOT NULL,
`liker_id` int(11) NOT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `uk_user_id_liker_id` (`user_id`,`liker_id`)
) ENGINE=InnoDB;

CREATE TABLE `friend` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`friend_1_id` int(11) NOT NULL,
`friend_2_id` int(11) NOT NULL,
UNIQUE KEY `uk_friend` (`friend_1_id`,`friend_2_id`),
PRIMARY KEY (`id`)
) ENGINE=InnoDB;

+------------------------------------+------------------------------------+
|session1(操作逻辑: A喜欢B)          |session2(操作逻辑: B喜欢A)          |
+------------------------------------+------------------------------------+
|begin;                              |                                    |
|select * from `like` where user_id=B|                                    |
|and liker_id = A; (返回空)          |                                    |
+------------------------------------+------------------------------------+
|                                    |begin;                              |
|                                    |select * from `like` where user_id=A|
|                                    |and liker_id=B; (返回空)            |
+------------------------------------+------------------------------------+
|                                    |insert into `like`(user_id,liker_id)|
|                                    |values(B,A);                        |
+------------------------------------+------------------------------------+
|insert into `like`(user_id,liker_id)|                                    |
|values(A,B);                        |                                    |
+------------------------------------+------------------------------------+
|commit;                             |                                    |
+------------------------------------+------------------------------------+
|                                    |commit;                             |
+------------------------------------+------------------------------------+

      上面的结果对业务来说就是bug了。因为在业务设定里面，这两个逻辑都执行完成以后， 是应该在friend表里面插入一行记录的。

      1. 如何解决记录不存在，行锁无法生效的问题？ 首先，要给"like"表增加一个字段，比如叫做relation_ship，并设为整型，取值1、2、3。
      值是1的时候，表示user_id关注liker_id;
值是2的时候，表示liker_id关注user_id;
值是3的时候，表示相互关注。

      然后，当A关注B的时候，逻辑改成如下所示的样子(注意，这里的A和B都是ID值)： 之所以要比较A和B的值，是为了保证"like"表中永远user_id<liker_id，这样不论是 A 关注 B， 还是 B 关注 A，在操作“like”表的时候，如果反向的关系已经存在，就会出现行锁冲突。 到底是A关注B还是B关注的A，由relation_ship字段来表示。

      • 如果A的值小于B的值，即A<B:
      1
2
3
4
5
6
7
8
9

      mysql> begin; /*启动事务*/
insert into `like`(user_id, liker_id, relation_ship) values(A, B, 1) on duplicate key update relation_ship=relation_ship | 1;
select relation_ship from `like` where user_id=A and liker_id=B;
/*代码中判断返回的 relation_ship，
如果是1，事务结束，执行 commit
如果是3，则执行下面这两个语句：
*/
insert ignore into friend(friend_1_id, friend_2_id) values(A,B);
commit;
      • A>B:
      1
2
3
4
5
6
7
8
9

      mysql> begin; /*启动事务*/
insert into `like`(user_id, liker_id, relation_ship) values(B, A, 2) on duplicate key update relation_ship=relation_ship | 2;
select relation_ship from `like` where user_id=B and liker_id=A;
/*代码中判断返回的 relation_ship，
如果是2，事务结束，执行 commit
如果是3，则执行下面这两个语句：
*/
insert ignore into friend(friend_1_id, friend_2_id) values(B,A);
commit;

邻接矩阵

邻接矩阵的底层依赖一个二维数组。

  • 对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j]和 A[j][i]标记为 1；
  • 对于有向图来说，
    • 如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，那我们就将 A[i][j]标记为 1。
    • 同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i]标记为 1。
  • 对于带权图，数组中就存储相应的权重。

用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。为什么这么说呢？

  • 对于无向图来说，
    • 如果 A[i][j]等于 1，那 A[j][i]也肯定等于 1。
    • 实际上，我们只需要存储一个就可以了。
    • 也就是说，无向图的二维数组中，如果我们将其用对角线划分为上下两部分，那我们只需要利用上面或者下面这样一半的空间就足够了，另外一半白白浪费掉了。
  • 如果我们存储的是稀疏图（Sparse Matrix），也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。

专题: 图

本文发表于 2021-07-18，最后修改于 2021-07-18。

本站永久域名「 jiavvc.top 」，也可搜索「 后浪笔记一零二四 」找到我。

上一篇 « Trie树 下一篇 » 广度和深度优先搜索

赞赏支持

请我吃鸡腿 =^_^=

i ysf

云闪付

i wechat

微信

推荐阅读

栈

发表于2021-07-15， 阅读约4分钟

Untitled

发表于0001-01-01， 阅读约1分钟

Untitled

发表于0001-01-01， 阅读约11分钟

Big Image