每周学点大数据 | 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. 王:关于图有很多的经典算法,比如单源最短路径、最小生成树等。在我们的讨论课中,我会给出这些经典算法的大数据版本。当然,在那之前,我会带你复习其经典版本。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2016-11-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

当七夕遇上算法竞赛

  七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去T...

14920
来自专栏安恒网络空间安全讲武堂

由suctf一道题学到的中国余子式定理

12630
来自专栏数据结构与算法

2017.10.23解题报告

预计分数:100+60+0=160 实际分数:100+80+0=180 T1 题目描述 现在有一个字符串,每个字母出现的次数均为偶数。接下来我们把第一次出现的字...

33850
来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

11430
来自专栏应兆康的专栏

100个Numpy练习【5】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

791120
来自专栏应兆康的专栏

100个Numpy练习【5】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

620100
来自专栏开发与安全

算法:堆栈与深度优先搜索(迷宫问题)

堆栈的访问规则被限制为Push和Pop两种操作,Push(入栈或压栈)向栈顶添加元素,Pop(出栈或弹出)则取出当前栈顶的元素,也就是说,只能访问栈顶元素而不能...

35490
来自专栏javascript趣味编程

5.2.1 二维导热算例-热导的概念

材料类,描述材料的参数,如密度、比热和初始温度等,这里特别给出了凝固潜热;这里要注意Math.pow(2,0)的意义,读者自己琢磨,用于判断相邻控制体的...

11400
来自专栏JadePeng的技术博客

从编辑距离、BK树到文本纠错

搜索引擎里有一个很重要的话题,就是文本纠错,主要有两种做法,一是从词典纠错,一是分析用户搜索日志,今天我们探讨使用基于词典的方式纠错,核心思想就是基于编辑距离,...

66660
来自专栏趣学算法

数据结构 第15讲 一场说走就走的旅行——最短路径

本内容来源于《趣学算法》,在线章节:http://www.epubit.com.cn/book/details/4825

35110

扫码关注云+社区

领取腾讯云代金券