和3条边的有向图]]
在计算机科学中，图（）是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。
图的数据结构包含一个有限（可能是可变的）的集合作为节点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边（有向图中也称作弧）的集合。节点可以是图结构的一部分，也可以是用整数下标或引用表示的外部实体。
图的数据结构还可能包含和每条边相关联的数值（），例如一个标号或一个数值（即权重，；表示花费、容量、长度等）。
操作
图数据结构G支持的基本操作通常包括：
- 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。
如果该数据结构支持和边关联的数值，则通常也支持下列操作
其它表示和存储图的数据结构还包括链式前向星、十字链表、等。
并行计算
图问题的并行计算主要存在如下几种困难：处理大量的数据、求解非常规的问题、数据不分散、数据存取对计算的比例很高等。面对这些困难，并行计算中图的表示和存储方式很重要。如果选取了不合适的表示方式，可能带来不必要的通讯花费，进而影响算法的可扩展性。在本节中，并行计算的共享和存储模型都在考虑之列。
共享存储
在共享存储模型下，图的表示和非并行计算中的场景是相同的，，因为在此模型下，对图表示（如邻接表）的并行读取操作效率已经足够高了。
分布式存储
在模型下，通常会采用点集V为p个集合V_0, \dots, V_{p-1}的方式，其中p是并行处理器的数量。随后，这些点集划分及相连的边按照标号分配给每个并行处理器。每个处理器存储原图的一个子图，而那些两个顶点分属两个子图的边则需额外特殊处理。在分布式图算法中，处理这样的边往往意味着处理器之间的通讯。但图划分本身就是NP难问题。因此，实践中会使用启发式方法。
图的压缩存储
机器学习、社会网络分析等领域中，有时会处理数万亿条边的图。图的压缩存储可以减少存取和内存压力。霍夫曼编码等一些数据压缩的常见方法是可行的。同时，邻接表、邻接矩阵等也有专门的压缩存储方法以提高效率。
参见
- 图遍历
- 图数据库
*
参考资料
外部链接
*[http://www.boost.org/libs/graph Boost Graph Library] ，一个C++的图程序库，例如Boost C++ Libraries。
*[https://networkx.org/ Networkx] ，一个Python图程序库。
*[http://graphblas.org GraphBLAS] ，一个图操作的应用程序接口说明。特别关注了稀疏图。
评论 (0)