图（抽象数据类型）

本词条由923397935初步翻译 由CecileLi初步审校 “表示方法”一目下表格中的部分文字没有翻译

一个有三个顶点（蓝色圆圈）和三条边（黑色箭头）的有向图。

在计算机科学中，图是一种抽象的数据类型，用来展现数学中图论领域中的无向图 undirected graph和有向图 directed graph的概念。

一个图的数据结构由一组有限的（也可能是可变的）顶点 vertices（也称为节点 nodes或点 points） ，以及一组无向图的无序顶点对或有向图的有序顶点对组成。这些连线被称为边 edges（也称为链接 links或直线 lines），对于有向图，也称为箭头 arrows。顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。

图形数据结构还可以为每条边关联一些边值 edge value，如符号标签或数字属性（成本、容量、长度等）。

操作方式 Operations

图形 G 的数据结构提供的基本操作通常包括：

• adjacent(G, x, y):检验顶点 x 到顶点 y 是否存在边；

• neighbors(G, x)：列出所有顶点 y ，使顶点 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 .

将值关联到边的结构通常还提供：

• get_edge_value(G, x, y): returns the value associated with the edge (x, y);

• set_edge_value(G, x, y, v): sets the value associated with the edge (x, y) to v.
• get_edge_value(G, x, y): 连接点 (x, y)的返回值;

• set_edge_value(G, x, y, v): 连接点(x, y) 到 v的设置值.

表示方法 Representations

在实际应用中不同数据结构的图表示方法:

• 邻接表 Adjacency list

顶点作为记录或存储对象，每个顶点存储一个相邻顶点列表。这种数据结构允许在顶点上存储额外的数据。如果边也被存储为对象，那么它就可以存储额外的数据，在这种情况下，每个顶点记录着它的关联边，每个边又存储它的关联顶点。

• 邻接矩阵 Adjacency matrix

一个二维矩阵，其中行表示源顶点 Source Vertices，列表示目标顶点 Destination Vertices。关于边和顶点的数据必须存储在外部。只有一条边时它可以被存储在每对顶点之间。

• 关联矩阵 Incidence matrix

一个二维布尔矩阵，其中行表示顶点，列表示边。矩阵的条目值 entries 表明行上的顶点是否与列上的边是相关联。

下表给出了在图上执行各种操作的时间复杂度 Time Complexity，对于每个表达式，用 | V | 顶点数和 | E | 边数。在矩阵表示中，条目值the entries跟随边的代价进行编码。假定不存在的边的值为∞。

	邻接表	邻接矩阵	关联矩阵
图的存储	[math]\displaystyle{ O(|V|+|E|) }[/math]	[math]\displaystyle{ O(|V|^2) }[/math]	[math]\displaystyle{ O(|V|\cdot|E|) }[/math]
添加顶点	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(|V|^2) }[/math]	[math]\displaystyle{ O(|V|\cdot|E|) }[/math]
添加边	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(|V|\cdot|E|) }[/math]
删除顶点	[math]\displaystyle{ O(|E|) }[/math]	[math]\displaystyle{ O(|V|^2) }[/math]	[math]\displaystyle{ O(|V|\cdot|E|) }[/math]
删除边	[math]\displaystyle{ O(|V|) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(|V|\cdot|E|) }[/math]
判断顶点 x 和 y 是否相邻(假设它们的存储位置已知)	[math]\displaystyle{ O(|V|) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(|E|) }[/math]
备注	因为顶点和边的删除操作需要找到所有的顶点或边，所以它的进行速度很慢，	增加或删除顶点速度慢，因为矩阵必须调整大小/复制	因为矩阵必须调整大小/或进行复制，所以增加或删除顶点和边时速度慢，

邻接表通常是首选的，因为它们能有效地表示稀疏图 Sparse Graph。如果图是稠密图 Dense Graph的，那么邻接矩阵是首选的，即边的数目 | E | 接近于顶点的平方数，| V |² ，或者说如果有一条边连接两个顶点，那么所选取的数据结构必须满足可以快速查找到数据。

图的并行化表示 Parallel Graph Representations

图问题的并行化面临着重大的挑战: 数据驱动的计算、非结构化问题、局部性差和计算数据访问率高。 用于并行架构的图表示在面对这些挑战时扮演着重要的角色。选择的表示方式不当可能会增加不必要的算法连接代价，从而降低算法的可扩展性。接下来的段落中，我们将着重探讨共享和分布式的内存架构。

共享内存 Shared memory

在共享内存模型下，之所以用于并行处理的图表示与顺序处理的方式相同，是因为对图表示的并行只读访问(例如：邻接表)是共享内存的有效方法。

分布式存储 distributed memory

在分布式存储模型中，常用的方法是将图的顶点集合[math]\displaystyle{ V }[/math] 分解为[math]\displaystyle{ p }[/math] 集合 [math]\displaystyle{ Vo,\dots,V{ p-1} }[/math] 。这里，[math]\displaystyle{ p }[/math] 是可用处理元素 processing elements（PE）的数量。然后，顶点集合分区被分配到具有匹配索引的 PE 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着连接通信。

图的划分需要仔细地进行——在低效率连接和大小划分之间有一个权衡。但是图的划分是一个NP-难问题 NP-Hard Problem，因此计算它们是不可行的。不过，我们可以使用以下启发式。

1D 分区: 每个处理器都会得到 [math]\displaystyle{ n/p }[/math] 顶点和相应的外边。这可以理解为按行或按列对邻接矩阵进行展开。对于在这种表示形式上运行的算法，需要一个 All-to-All 连接步骤以及 [math]\displaystyle{ mathcal{o}(m) }[/math] 消息缓冲区大小，因为每个 PE 可能具有相对于其他 PE 的输出边。

2D分区: 每个处理器都有一个邻接矩阵的子矩阵。假设处理器在一个矩形[math]\displaystyle{ p = p_r \times p_c }[/math] 中对齐，其中 [math]\displaystyle{ p_r }[/math]和[math]\displaystyle{ p_c }[/math]是每行和每列中处理元素的数量。然后每个处理器得到维数[math]\displaystyle{ (n/p_r)\times(n/p_c) }[/math] 的邻接矩阵。这可以可视化为矩阵中的棋盘格模式。因此，每个处理单元只能在同一行和列中具有 PE 的输出边。这将每个 PE 的通信伙伴的数量限制为 [math]\displaystyle{ p_r + p_c - 1 }[/math] 出[math]\displaystyle{ p = p_r \times p_c }[/math]可能的伙伴

参见

• 图的遍历 Graph traversal 用于图遍历的策略
• 图数据库 Graph database 用于图（数据结构）的持久性
• 图重构 Graph rewriting 用于基于规则的图形转换（图数据结构）
• 画图软件 Graph drawing software 用于绘制图形的软件、系统和系统提供商

其他链接

• Boost Graph Library: a powerful C++ graph library s.a. Boost (C++ libraries)

• Networkx: a Python graph library

• GraphMatcher a java program to align directed/undirected graphs.

• GraphBLAS A specification for a library interface for operations on graphs, with a particular focus on sparse graphs.