图 (数据结构)
在电脑科学中,图(英语:graph)是一种抽象数据类型,用于实现数学中图论的无向图和有向图的概念。
图的数据结构包含一个有限(可能是可变的)的集合作为节点集合,以及一个无序对(对应无向图)或有序对(对应有向图)的集合作为边(有向图中也称作弧)的集合。节点可以是图结构的一部分,也可以是用整数下标或引用表示的外部实体。
图的数据结构还可能包含和每条边相关联的数值(edge value),例如一个标号或一个数值(即权重,weight;表示花费、容量、长度等)。
操作
图数据结构G支持的基本操作通常包括:[1]
adjacent
(G, x, y):查看是否存在从节点x到y的边;neighbors
(G, x):列出所有从x出发的边的另一个顶点y;add_vertex
(G, x):如果不存在,将节点x添加进图;remove_vertex
(G, x):如果存在,从图中移除节点x;add_edge
(G, x, y):如果不存在,添加一条从节点x到y的边;remove_edge
(G, x, y):如果存在,从图中移除从节点x到y的边;get_vertex_value
(G, x):返回节点x上的值;set_vertex_value
(G, x, v):将节点x上的值赋为v。
如果该数据结构支持和边关联的数值,则通常也支持下列操作[1]:
get_edge_value
(G, x, y):返回边(x, y)上的值;set_edge_value
(G, x, y, v):将边(x, y)上的值赋为v。
图的常见数据结构
- 邻接表[2][3]
- 节点存储为记录或对象,且为每个节点创建一个列表。这些列表可以按节点存储其余的资讯;例如,若每条边也是一个对象,则将边存储到边起点的列表上,并将边的终点存储在边这个的对象本身。
- 邻接矩阵[4][5]
- 一个二维矩阵,其中行与列分别表示边的起点和终点。顶点上的值存储在外部。矩阵中可以存储边的值。
- 关联矩阵[6]
- 一个二维矩阵,行表示顶点,列表示边。矩阵中的数值用于标识顶点和边的关系(是起点、是终点、不在这条边上等)。
下表给出了在图上进行各种操作的复杂度。其中,用|V|表示节点数量,|E|表示边的数量。同时假设存储的资讯是边上对应的值,如果没有对应值则存储∞。
邻接表 | 邻接矩阵 | 关联矩阵 | |
---|---|---|---|
空间复杂度 [7] | |||
存储一张图 | |||
时间复杂度 [8] | |||
添加节点 | |||
添加边 | |||
移除节点 | |||
移除边 | |||
检查节点x和y是否邻接(假设已知两个节点对应的存储位置) | |||
注释 | 移除节点或边速度较慢,因为需要找到相连的边或节点 | 增减节点速度较慢,因为需要修改矩阵的大小 | 增减节点或边速度较慢,因为需要修改矩阵的大小 |
邻接表在稀疏图上比较有效率。邻接矩阵则常在图比较稠密的时候使用,判断标准一般为边的数量|E |接近于节点的数量的平方|V |2;邻接矩阵也在查找两节点邻接情况较为频繁时使用。[9][10]
其它表示和存储图的数据结构还包括链式前向星、十字链表、邻接多重表等。
并行计算
图问题的并行计算主要存在如下几种困难:处理大量的数据、求解非常规的问题、数据不分散、数据存取对计算的比例很高等。[11][12]面对这些困难,并行计算中图的表示和存储方式很重要。如果选取了不合适的表示方式,可能带来不必要的通讯花费,进而影响算法的可扩展性。在本节中,并行计算的共享和分布式存储模型都在考虑之列。
共享存储
在共享存储模型下,图的表示和非并行计算中的场景是相同的,[13],因为在此模型下,对图表示(如邻接表)的并行读取操作效率已经足够高了。
分布式存储
在分布式存储模型下,通常会采用划分点集为个集合的方式,其中是并行处理器的数量。随后,这些点集划分及相连的边按照标号分配给每个并行处理器。每个处理器存储原图的一个子图,而那些两个顶点分属两个子图的边则需额外特殊处理。在分布式图算法中,处理这样的边往往意味着处理器之间的通讯。[13]
图的划分需要谨慎地在降低通讯复杂度和使划分均匀之间取舍。[14]但图划分本身就是NP难问题。因此,实践中会使用启发式方法。
图的压缩存储
机器学习、社会网络分析等领域中,有时会处理数万亿条边的图。图的压缩存储可以减少存取和内存压力。霍夫曼编码等一些数据压缩的常见方法是可行的。同时,邻接表、邻接矩阵等也有专门的压缩存储方法以提高效率。[15]
参见
参考资料
- ^ 1.0 1.1 参见Goodrich & Tamassia (2015), Section 13.1.2: Operations on graphs, p. 360。更多细节也可参见Mehlhorn, K.; Näher, S., Chapter 6: Graphs and their data structures, LEDA: A platform for combinatorial and geometric computing, Cambridge University Press: 240–282, 1999.
- ^ Cormen et al. 2001,第528–529页.
- ^ Goodrich & Tamassia 2015,第361-362页.
- ^ Cormen et al. 2001,第529–530页.
- ^ Goodrich & Tamassia 2015,第363页.
- ^ Cormen et al. 2001,Exercise 22.1-7, p. 531.
- ^ Cormen et al. 2001,第589-591页.
- ^ Goodrich & Tamassia 2015,§13.1.3.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Section 22.1: Representations of graphs, Introduction to Algorithms Second, MIT Press and McGraw-Hill: 527–531, 2001, ISBN 0-262-03293-7.
- ^ Goodrich, Michael T.; Tamassia, Roberto, Section 13.1: Graph terminology and representations, Algorithm Design and Applications, Wiley: 355–364, 2015.
- ^ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea. Graph Partitioning and Graph Clustering. Contemporary Mathematics 588. American Mathematical Society. January 2013. ISBN 978-0-8218-9038-7. doi:10.1090/conm/588/11709 (英语).
- ^ LUMSDAINE, ANDREW; GREGOR, DOUGLAS; HENDRICKSON, BRUCE; BERRY, JONATHAN. Challenges in Parallel Graph Processing. Parallel Processing Letters. March 2007, 17 (1): 5–20. ISSN 0129-6264. doi:10.1142/s0129626407002843.
- ^ 13.0 13.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman. Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer International Publishing. 2019 [2021-08-14]. ISBN 978-3-030-25208-3. (原始内容存档于2021-08-17) (英语).
- ^ Parallel Processing of Graphs (PDF). [2021-08-14]. (原始内容存档 (PDF)于2021-08-25).
- ^ Besta, Maciej; Hoefler, Torsten. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. 27 April 2019. arXiv:1806.01799 .
外部链接
- Boost Graph Library (页面存档备份,存于互联网档案馆),一个C++的图程序库,例如Boost_C++_Libraries。
- Networkx (页面存档备份,存于互联网档案馆),一个Python图程序库。
- GraphBLAS (页面存档备份,存于互联网档案馆),一个图操作的应用程序接口说明。特别关注了稀疏图。