数据结构与算法之美 | 学习笔记26 —— 图的表示
一、图（Graph）的定义
除了树之外，另一种非线性数据表结构：图。图中的元素叫顶点（vertex），顶点与其他的顶点建立的连接关系叫边（edge）。跟顶点连接的边的条数为度（degree）。
无向图：
有向图：
入度（In-degree）：表示有多少条边指向这个顶点；
入度（Out-degree）：表示有多少条边以这个顶点为起点指向其他顶点；
带权图（Weighted graph）：
二、图的存储
1. 邻接矩阵（Adjacency Matrix）
存储一个二维数组，如果顶点i和顶点j之间有边，对应A[i][j]标记为1或对应权重；所以对于无向图，矩阵关于对角线对称，另一半的存储空间属于浪费了，并且如果边不多，这个稀疏矩阵的利用效率也不高。
但好处在于：存储方式简单直接，方便矩阵之间的计算，例如求解最短路径时的Floyd-Warshall算法。
2. 邻接表（Adjacency List）
这个结构类似散列表，每个顶点对应一条链表，链表中存储与这个顶点相连接的其他顶点。存储省空间，但使用耗时。同时我们可以对其进行改造，比如将其中链表改为平衡二叉查找树，跳表、动态数组等。
三、图的应用
如何储存微博的好友关系？
- 社交网络是一张稀疏图，用邻接表存储较好。如果要统计用户的粉丝列表，就需要另外一个逆邻接表。
- 基础的邻接表不适合快速判断两个用户是关注与被关注，所以可以将邻接表中的链表改为支持快读查找的动态数据结构。
- 如要按照用户名首字母排序，分页获取用户的粉丝列表或关注列表，可以使用跳表，这种针对于小规模的数据，比如社交网络中有几万或几十万个用户。
- 如果是大规模数据，可以先用哈希算法等数据分片方式，将邻接表存储在不同机器上，存储方式如下图：
这样，在查询顶点与顶点关系时，先定位顶点所在机器，再进行查找。 - 另外，可以用外部存储如硬盘。比如数据库用表来存储一张图，数据库是我们经常用来持久化存储关系数据的。