如何理解“图”？

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

图

无向图

我们就拿微信举例子吧。我们可以把每个用户看作一个顶点。如果两个用户之间互加好友，那就在两者之间建立一条边。所以，整个微信的好友关系就可以用一张图来表示。其中，每个用户有多少个好友，对应到图中，就叫作顶点的度（degree），就是跟顶点相连接的边的条数。

有向图

无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图中，我们把度分为入度（In-degree）和出度（Out-degree）。

有向图

顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。对应到微博的例子，入度就表示有多少粉丝，出度就表示关注了多少人。

带权图

在带权图中，每条边都有一个权重（weight），我们可以通过这个权重来表示QQ好友间的亲密度。

带权图

邻接矩阵存储方法

邻接矩阵（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。对于带权图，数组中就存储相应的权重。

邻接矩阵

邻接表（Adjacency List）

邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是使用起来就比较耗时间。

邻接表