图 (数据结构)

✍ dations ◷ 2024-12-23 14:34:02 #图 (数据结构)

在计算机科学中,图(英语:graph)是一种抽象数据类型,用于实现数学中图论的无向图和有向图的概念。

图的数据结构包含一个有限(可能是可变的)的集合作为节点集合,以及一个无序对(对应无向图)或有序对(对应有向图)的集合作为边(有向图中也称作弧)的集合。节点可以是图结构的一部分,也可以是用整数下标或引用表示的外部实体。

图的数据结构还可能包含和每条边相关联的数值(edge value),例如一个标号或一个数值(即权重,weight;表示花费、容量、长度等)。

图数据结构支持的基本操作通常包括:

如果该数据结构支持和边关联的数值,则通常也支持下列操作:

下表给出了在图上进行各种操作的复杂度。其中,用||表示节点数量,||表示边的数量。同时假设存储的信息是边上对应的值,如果没有对应值则存储∞。

邻接表在稀疏图(英语:sparse graph)上比较有效率。邻接矩阵则常在图比较稠密的时候使用,判断标准一般为边的数量| |接近于节点的数量的平方| |2;邻接矩阵也在查找两节点邻接情况较为频繁时使用。

其它表示和存储图的数据结构还包括链式前向星、十字链表、邻接多重表(英语:adjacency multilist)等。

图问题的并行计算主要存在如下几种困难:处理大量的数据、求解非常规的问题、数据不分散、数据存取对计算的比例很高等。面对这些困难,并行计算中图的表示和存储方式很重要。如果选取了不合适的表示方式,可能带来不必要的通讯花费,进而影响算法的可扩展性。在本节中,并行计算的共享和分布式(英语:distributed memory)存储模型都在考虑之列。

在共享存储模型下,图的表示和非并行计算中的场景是相同的,,因为在此模型下,对图表示(如邻接表)的并行读取操作效率已经足够高了。

在分布式存储(英语:distributed memory)模型下,通常会采用划分(英语:graph partition)点集 V {displaystyle V} p {displaystyle p} 个集合 V 0 , , V p 1 {displaystyle V_{0},dots ,V_{p-1}} 的方式,其中 p {displaystyle p} 是并行处理器的数量。随后,这些点集划分及相连的边按照标号分配给每个并行处理器。每个处理器存储原图的一个子图,而那些两个顶点分属两个子图的边则需额外特殊处理。在分布式图算法中,处理这样的边往往意味着处理器之间的通讯。

图的划分需要谨慎地在降低通讯复杂度和使划分均匀之间取舍。但图划分本身就是NP难问题。因此,实践中会使用启发式方法。

机器学习、社会网络分析等领域中,有时会处理数万亿条边的图。图的压缩存储可以减少存取和内存压力。霍夫曼编码等一些数据压缩的常见方法是可行的。同时,邻接表、邻接矩阵等也有专门的压缩存储方法以提高效率。

相关

  • 国家侦查局美国国家侦察局(National Reconnaissance Office,NRO),位于美国维吉尼亚州,是美国的16个情报机构之一;负责为美国政府设计、组装并发射侦察卫星。 并协调、收集和分析从中央情报
  • 布罗克顿市布罗克顿(英语:Brockton)位于美国马萨诸塞州东南部,是普利茅斯县的县治所在,面积55.9平方公里。根据2010年美国人口普查,共有93,810人,其中白人占46.7%、非裔美国人占31.2%、亚裔美
  • 北极光北极光可以指:
  • 医疗旅游医疗旅游是指借由旅游到国外医疗救治的活动,在过去进行医疗旅游的人大多从发展中国家前往发达国家。但是,现在也有前往低治疗价格国家进行医疗旅游的现象。原因可能是他们寻求
  • 大园区坐标:25°3′45.52″N 121°11′52.32″E / 25.0626444°N 121.1978667°E / 25.0626444; 121.1978667大园区(台湾客家语饶平腔:taiˊ vien kiˇ;台湾话:.mw-parser-output .sans
  • BOYFRIEND in Wonderland《BOYFRIEND in Wonderland》是韩国的男子组合BOYFRIEND第4枚迷你韩语专辑,于2015年3月9日发行,主打歌曲为《BOUNCE》。2015年2月23日,STARSHIP娱乐在Youtube发放了一段荣旻和
  • 旅行青蛙《旅行青蛙》(日语:旅かえる,又译作“旅青蛙”、“旅蛙”)是一款由日本游戏公司Hit-Point开发的一款iOS及Android智能手机游戏,Android版发行于2017年11月24日,iOS版发行于2017年1
  • 图努帕火山图努帕火山是玻利维亚的火山,位于该国西南部乌尤尼盐沼以北,由奥鲁罗省和波托西省负责管辖,属于安第斯山脉的一部分,海拔高度5,432米。
  • 附带意见附带意见(拉丁语单数:Obiter dictum,拉丁语复数 obiter dicta),又称判词旁论,指法官或仲裁员在判决书中不具拘束力,“附带”的论述。附带意见的概念源自英国普通法,将判决书分为具有约束力的“判决理由”(ratio decidenti)以及不具约束力(但具有说服力)的附带意见。Obiter dicta 拉丁语的字面意思是“说的其他内容”。英语中根据地区不同,通常简称为 obiter 或 dicta。司法判决书的内容只有在涉及案件的关键事实和法律时,才能成为判决理由。不重要的、涉及假设性
  • 行政院农业委员会畜产试验所行政院农业委员会畜产试验所(简称畜试所),成立于1940年,位于台南市新化区。并设有新竹、宜兰等7处分所、场,负责台湾畜产试验研究工作。未来随农业部成立后将更名为农业部畜产试验所。