每周学点大数据 | No.15 图在计算机中的存储

No.15期

图在计算机中的存储

Mr. 王：还有一个很重要的问题，就是图在计算机中的表示。虽然我们看到的图边和点等都是非常直观的，可以画成一个圆圈里带一个数字表示顶点，用一条带有数字的线段或者箭头来表示边，但是在计算机中，显然不能用这种方式来存储它。

小可开玩笑地说：要是把图存成图片，那可太占空间了，而且还不容易读取上面的数字。

Mr. 王：是啊，图已经是对现实世界的一个抽象了，在计算机中我们要对其进行进一步的抽象。你想一想，图由哪两部分组成？

小可：边的集合和顶点的集合。

Mr. 王：在手绘的图中，对于顶点的位置和表示边的线段的长度都是没有任何影响的。对于顶点，我们只关注它的编号（ID）和权值；对于边，我们只关注它连接的两个顶点和权值。当然，对于有向图来说，还有方向。

小可：这是不是意味着，我们只需要存储这些信息就可以了？

Mr. 王：是的。不仅如此，我们还希望这些边和点的集合可以被更高效地发现，比如举出一个顶点，就可以很快地找到它的邻居们。所以直接存储所有的边和顶点查询效率不够高，因此计算机工作者们选取了邻接矩阵和邻接表。

小可：那什么是邻接矩阵呢？

Mr. 王：邻接矩阵是这样的，它是一个方阵，行和列这两组表头分别是所有顶点的ID。

比如一个图有A,B,C,D,E这些节点，我们就在行表头记ABCDE，相应的，也在列表头记ABCDE，这样就有了所有的节点。如果这些节点还有权值，那么就记在另一张表中。实际存储在计算机中时，我们会用一个二维数组来表示，其中A,B,C,D,E这些字母用数组下标0,1,2,3,4来表示。

小可：那么如何来表示一条边呢？

Mr. 王：数组内存储的数据还是空的，我们就用这个数据域来表示边。假如有一条有向边AB，它的权值为5，我们就将数组G[0][1]这个位置填充数据5即可，对于权值为6的边BC，G[1][2]=6。相应的，如果有一条有向边BA，它的权值为4，我们就将G[1][0]填充为4。

邻接矩阵的例子

小可：那么如何表示无向边呢？

Mr. 王：在邻接矩阵的表示中，一般不去区分有向图和无向图。无向图的表示方法和有向图是一致的，只不过在无向图中，对于长度为3的无向边AB，我们将G[1][0]和G[0][1]的值都改为3即可。在这里，其实一条无向边可以看作，两条方向相反、权值相等、连接相同两个顶点的有向边。

无向图的邻接矩阵

小可：那些没有边的数据域呢？

Mr. 王：一般来说，我们会用权值来表示两个顶点的距离。如果没有边，那么这两个点之间的距离可以看作是无穷大。在实际应用中，我们会用一个很大的数来表示它，对于每个顶点到自己的距离，一般记作0，比如G[0][0]=0，这样可以方便很多算法的处理。另外，对于无权的图，我们将边的权值视作1，这样方便计算无权图中路径的长度，也就是经过边的数量。

小可：可是邻接矩阵占用空间很大啊，不论两个顶点之间是不是真的有一条边，我们都要用一个数来存储。这岂不是很浪费空间吗？

Mr. 王：所以邻接矩阵更加适合用来存储稠密图，图中的边越多，浪费的空间就越少。

小可：对于那些比较稀疏的图，怎么办呢？

Mr. 王：这就要使用另一种存储结构——邻接表。邻接表比较适合用于存储稀疏的图。邻接表是一个链表的集合，链表所有的表头代表一个节点。比如前面的例子有A,B,C,D,E这5个节点，在这个集合中建立5个链表，分别代表这5个节点，然后将每个节点的所有邻居作为元素插入到链表中。假如AB有一条边的权值是5，我们就在A 的这个链表中存储节点B，并记下值为5即可；BC有一条边权的值为6，我们就在B这个链表中存储节点C，并记下值为6即可。

邻接表

小可：嗯，有边就记录，没有边就不记录，这样确实很节省存储空间。

Mr. 王：不过邻接表也不是完美的，当图比较稠密的时候，图中的边就特别的多，链表中的元素也就特别的多。链表上不止有数据域，还有一个指针，相比邻接矩阵，这个指针完全是浪费空间的，它没有存储任何与图有关的内容。所以对于稠密图，邻接矩阵的表现不佳。

综合来看，这两种存储结构是各有优缺点的，不能单纯地说哪一种结构就优于另一种结构。这种道理也是普遍存在的，没有完美的结构，只有最适合的结构。这要看具体的数据规模、结构情况和使用的算法更适合于哪一种结构来进行选择，才能更节省空间或者时间来更好地解决问题。

Mr. 王：关于图有很多的经典算法，比如单源最短路径、最小生成树等。在我们的讨论课中，我会给出这些经典算法的大数据版本。当然，在那之前，我会带你复习其经典版本。

内容来源：灯塔大数据