如何理解“图” （graph）
先来了解一下图的几个概念：
顶点(vertex)、边(edge)、度(degree)、有向图、无向图、入度(in-degree)、出度(out-degree)、带权图(weighted-graph)
再来利用微博、微信、QQ来形象的诠释一下这几个概念：
微信：把用户比作顶点，如果两个用户之间互加好友，那就在两者之间建立一条边，所以整个微信好友关系就是一张图， 每个用户有多少好友，就对应到图中每个顶点的度。
微博：社交关系更复杂，允许单向关注，即A关注B，但B可以不关注A，这里引用“方向”的概念。A关注B，画一条A指向B 的边，B关注A，再画一条B指向A的边。像这样，把边有方向的图叫有向图，把边无方向的图叫无向图。另外，A关注了多少人，叫顶点A的出度，A有多少粉丝，叫顶点A的入度。
QQ：社交关系也很复杂，QQ除了记录用户之间的好友关系，还有亲密度的功能，即用户之间经常来往，亲密度就高，不经常来往，亲密度就低。在图中，给每条边设一个权重(weight)来表示这种亲密度。
存储方法（邻接矩阵和邻接表）
邻接矩阵：用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。
对于无向图来说，如果顶点i和顶点j之间有边。就将A[i][j]和A[j][i]标记为1；对于有向图来说，如果有 i 指向j 的边，就将A[i][j]标记为1，同理，如果有j 指向i的边，我们就将A[j][i]标记为1。 如果是带权图，数组中就存储相应权重。
对于无向图来说，A[i][j] 和 A[j][i]是一个意思，将对角线把矩阵一分为二，只需一半空间就足够，另外一半就浪费了。如果 我们存储的是稀疏图，顶点多但边不多，所以很浪费空间。比如微信有好几亿用户，但是用户好友只有三五百人，如果用邻接矩阵，绝大部分空间都浪费了。但是它也有它的优点，首先，存储方式简单、直接，因为基于数组，取两个定点关系非常高效；其次，方便计算，可以将图之间的运算转化为矩阵之间的运算。
邻接表：乍一看，有点像散列表，每个顶点对应一条链表，链表中存放有对应连接关系链表，下图是一个有向图的邻接表 存储方式，每个顶点对应链表里边存储的是指向的顶点。对于无向图，存储的就是相连的顶点，说法不同而已。
邻接表与邻接矩阵特点正好相反，比较省空间，但是使用起来比较耗时间。这里我们可以改造链表为更高效的查找数据结 构，如平衡二叉查找树、跳表、散列表、有序的动态数组（通过二分查找快速定位两个顶点之间是否存在边）。
系统分析如何存储微博、微信等社交网络中好有关系
微博：先来看下微博的部分功能操作：
判断用户A是否关注了用户B；
判断用户A是否被用户B关注；
用户A关注用户B；
用户A取消关注用户B；
根据用户名称的首字母排序，分页获取用户的粉丝列表；
根据用户名称的首字母排序，分页获取用户的关注列表。
这里单张邻接表存储这种有向图肯定是不够，因为单单只能获取用户的关注列表，很难去获取用户的被关注列表，需要引 入一个逆邻接表。逆邻接表用来获取用户的被关注列表，也就是粉丝列表，在每个顶点的链表中，存储的是指向这个顶点的顶点。但这两张表只能算是基础的邻接表，不能快速的判断用户之间的关注与被关注关系，可以将邻接表改为可以支持快速查找的动态数据结构。因为我们需要根据用户名称的首字母排序，分页获取用户的粉丝列表和关注列表，用跳表会非常合适，因为跳表本身支持快速插入、查询、删除操作，时间复杂度O(logn)，空间复杂度O(n)。
这里仍然有一个问题，如果只是小规模数据，几万到几十万，上述方式没有问题，可以放到内存中操作。但是如果用户规 模达到几亿人，就无法全部存储到内存中，这里我们可以通过哈希算法等数据分片方式，将顶点对应的邻接表存储到不同机器当中，逆邻接表也一样。当我们需要查询顶点与顶点的关系，先用哈希算法定位顶点所在机器，再在相应机器查找。
微信：和微博相比较，微信的类似上述操作会更简单：
判断用户A和B是否是好有关系；
用户A加B为好友；
据根据用户名称的首字母排序，获取用户的好友列表。
因为是无向图，这里只需要一张邻接表存储与顶点相连的顶点，同时为了支持快速查找，可以使用红黑树、跳表等动态的 数据结构。
最后，以上说的都是在内存中存储，如果要持久化存储，可以选用关系型数据库，如果是超大图，以及要进行大量图计算，可以选用专业的图数据库。
以上所述，是本人最近在极客时间上学习数据结构和算法相关课程做的笔记吧。
具体参照：/column/intro/126
