图的表示法——邻接矩阵#

一、引言#

上一章节我们演示了如何利用两个动态列表来实现图的顶点存储和边存储，但是那样并不高效。

边的空间复杂度在最坏的情况下能达到顶点数量的平方，所以这个方法对于图的实现并不是很好的选择。

一种可以解决的方法就是利用二维矩阵，大小是顶点的平方——V**2。

二、邻接矩阵初尝试（无权重）#

我们对于顶点的存储依然可以利用先前的列表那种，二维矩阵则可以用来存储边。

我们先忽略权重的大小，将注意力转到顶点与顶点之间的边上面。

我们的顶点的索引的取值范围可以是0——v-1，对于边如何存储，我们可以采用以下方案。

对于Aij的值只有0和1两种，1用来表示两个边是从i到j的，0则是假代表没有连接。

下面我们来给这个二维矩阵填满吧😭

填完之后就是这个样子，因为是无向图，所以i-j和j-i是等价的。

其余没有填入数字的空格均为0，问就是懒得画了😎

所以事实上我们要找到这张图里的所有的边，只需要将这个矩阵对半砍一刀（沿着对角线砍）就可以了。

对于这个列表来说，找到一个顶点的相邻顶点的时间复杂度又是多少呢？

举个栗子，比如我们要找到顶点F的所有相邻顶点。

首先给定一个顶点的名字，我们首先要拿到它的索引。

索引可以通过遍历顶点列表来获取，F的索引我们拿到了，是5。

接着我们可以扫描这一行来找到所有邻居顶点。

在顶点列表中，我们遍历的时间复杂度是O(V),在右侧边矩阵里，我们找到相邻顶点的时间复杂度是O(v),

所以时间复杂度是O（v).

一个优化方法就是不要总是去遍历左边的列表，如果我们事先知道顶点的索引，那么我们就能在常数时间里找到它的名字。

现在判断两个顶点是否相互连接的时间成本是多少呢？

如果顶点名称按照索引给出，那么我们能直接在右边矩阵里找到对应行列里的值。

这花费的也是常数时间O（1）。

但是如果没有给出，我们依然要遍历左边的列表，所以会是O(v)。

为了找到索引而总是扫描列表，这样根本就是浪费时间，完全可以避免。

我们可以使用哈希表来映射顶点与索引的关系。

三、邻接矩阵（有权重）#

对于没有权重的图，我们直接利用了布尔值来表示边。

那么对于有权重的图，我们可以使用权重来填入Aij。

对于不存在的边，我们可以把权重设置为一个非常大的默认值。

四、反思#

我们使用了邻接矩阵，极大地降低了时间复杂度。

但是我们的空间复杂度几乎可以说是翻倍了，现在内存单元的使用不再等于边的数量，而是v的平方。

我们不仅存储了节点连接的信息，也存储了节点没有连接的信息，这是冗余的。

如果一个图很稠密，那么边的数量接近v的平方，那么这是完全没影响的。

但是如果图很稀疏，那么将会造成内存浪费。

好比微信，我只有50个不到的好友，但是微信有亿级的用户，那么我和其他用户没有关系，也要被存储下来吗？😱

所以像是一个非常大的社交网络，邻接矩阵法不是很有效呢。

而现实是大多数的图都是稀疏的，所以邻接矩阵并不合适。

下一篇文章，我们将讨论更好的解决方式，下次再见，嘿嘿嘿。