如何理解“图”（Graph）？

树中的元素我们称为节点，图中的元素我们就叫做顶点（vertex）。
图中的一个顶点可以与任意其他顶点建立连接关系，我们把这种建立的关系叫做边（edge）。
顶点的度（degree），就是跟顶点相连接的边的条数。
边有方向的图叫做“有向图”，边没有方向的图就叫做“无向图”。
无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图中，我们把度分为入度（In-degree）和出度（Out-degree）。
顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。
带权图（weighted graph），每条边都有一个权重（weight）。

图的存储方法

存储方法：邻接矩阵（Adjacency Matrix）

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

邻接矩阵存储.png
用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。
如果我们存储的是稀疏图（Sparse Matrix），也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户，对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多，一般也就三五百个而已。如果我们用邻接矩阵来存储，那绝大部分的存储空间都被浪费了。
邻接矩阵存储方法的优点：

首先，邻接矩阵的存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。
其次，用邻接矩阵存储图的另外一个好处是方便计算。
这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算。

存储方法：邻接表（Adjacency List）

邻接表存储.png

在基于链表法解决冲突的散列表中，如果链过长，为了提高查找效率，我们可以将链表换成其他更加高效的数据结构，比如平衡二叉查找树等。邻接表长得很像散列。所以，我们也可以将邻接表同散列表一样进行“改进升级”。
我们可以将邻接表中的链表改成平衡二叉查找树。实际开发中，我们可以选择用红黑树。这样，我们就可以更加快速地查找两个顶点之间是否存在边了。当然，这里的二叉查找树可以换成其他动态数据结构，比如跳表、散列表等。除此之外，我们还可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。

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

极客时间--数据结构与算法之美--30 | 图的表示：如何存储微博、微信等社交网络中的好友关系？