图 (数据结构)

  此條目介紹的是抽象数据类型。关于圖論中的基本研究對象，请见「图 (数学)」。关于數學函數的圖，请见「函数图形」。关于其他主題，请见「图」。

在计算机科学中，图（英語：graph）是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。

一个有3个节点和3条边的有向图

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

图的数据结构还可能包含和每条边相关联的数值（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]

一个二维矩阵，其中行与列分别表示边的起点和终点。顶点上的值存储在外部。矩阵中可以存储边的值。

关联矩阵（英语：incidence matrix）^[6]

一个二维矩阵，行表示顶点，列表示边。矩阵中的数值用于标识顶点和边的关系（是起点、是终点、不在这条边上等）。

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

	邻接表	邻接矩阵	关联矩阵
空间复杂度 ^[7]
存储一张图	${\displaystyle O(|V|+|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
时间复杂度 ^[8]
添加节点	${\displaystyle O(1)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
添加边	${\displaystyle O(1)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
移除节点	${\displaystyle O(|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
移除边	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
检查节点x和y是否邻接（假设已知两个节点对应的存储位置）	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|E|)}$
注释	移除节点或边速度较慢，因为需要找到相连的边或节点	增减节点速度较慢，因为需要修改矩阵的大小	增减节点或边速度较慢，因为需要修改矩阵的大小

邻接表在稀疏图（英语：sparse graph）上比较有效率。邻接矩阵则常在图比较稠密的时候使用，判断标准一般为边的数量|E |接近于节点的数量的平方|V |²；邻接矩阵也在查找两节点邻接情况较为频繁时使用。^[9][10]

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

并行计算

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

共享存储

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

分布式存储

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

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

图的压缩存储

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

参见

• 图遍历
• 图数据库
• 图绘制（英语：Graph drawing）

参考资料

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 .
2. Cormen et al. 2001，第528–529頁.
3. Goodrich & Tamassia 2015，第361-362頁.
4. Cormen et al. 2001，第529–530頁.
5. Goodrich & Tamassia 2015，第363頁.
6. Cormen et al. 2001，Exercise 22.1-7, p. 531.
7. Cormen et al. 2001，第589-591頁.
8. Goodrich & Tamassia 2015，§13.1.3.
9. 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 .
10. Goodrich, Michael T.; Tamassia, Roberto, Section 13.1: Graph terminology and representations, Algorithm Design and Applications, Wiley: 355–364, 2015 .
11. 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 （英语）. 
12. 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. 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） （英语）. 
14. Parallel Processing of Graphs (PDF). [2021-08-14]. （原始内容 (PDF)于2021-08-25）. 
15. 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 （页面存档备份，存于互联网档案馆），一个图操作的应用程序接口说明。特别关注了稀疏图。