微博、微信等社交网络中的好友关系是如何存储的？

如何理解“图”？

和树比起来，这是一种更加复杂的非线性表结构。

图中的元素我们就叫做顶点（vertex）。

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

跟顶点相连接的边的条数，叫做度（degree）。

上面的图为 无向图， 还有一种 有向图。

有向图中，我们把度分为入度（In-degree）和出度（Out-degree）。

此外还有一种图，带权图（weighted graph）

邻接矩阵存储方法

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

邻接矩阵在存储 稀疏图 时会造成存储空间浪费的问题。

邻接表存储方法

针对上面邻接矩阵比较浪费内存空间的问题，我们来看另外一种图的存储方法，邻接表（Adjacency List）。

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

内容总结

邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，邻接表还有改进升级版，即将链表换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。