图(抽象数据类型)
在计算机科学中,图是一种抽象的数据类型,用来展现数学中图论领域中的无向图 undirected graph和有向图 directed graph的概念。
一个图的数据结构由一组有限的(也可能是可变的)顶点 vertices(也称为节点 nodes或点 points) ,以及一组无向图的无序顶点对或有向图的有序顶点对组成。这些连线被称为边 edges(也称为链接 links或直线 lines),对于有向图,也称为箭头 arrows。顶点可以是图结构的一部分,也可以是由整数索引或引用表示的外部实体。
图形数据结构还可以为每条边关联一些边值 edge value,如符号标签或数字属性(成本、容量、长度等)。
操作方式 Operations
图形 G 的数据结构提供的基本操作通常包括:[1]
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 。
将值关联到边的结构通常还提供:[1]
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
在实际应用中不同数据结构的图表示方法:
- 顶点作为记录或存储对象,每个顶点存储一个相邻顶点列表。这种数据结构允许在顶点上存储额外的数据。如果边也被存储为对象,那么它就可以存储额外的数据,在这种情况下,每个顶点记录着它的关联边,每个边又存储它的关联顶点。
- 一个二维矩阵,其中行表示源顶点 Source Vertices,列表示目标顶点 Destination Vertices。关于边和顶点的数据必须存储在外部。只有一条边时它可以被存储在每对顶点之间。
- 一个二维布尔矩阵,其中行表示顶点,列表示边。矩阵的条目值 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 |2 ,或者说如果有一条边连接两个顶点,那么所选取的数据结构必须满足可以快速查找到数据。[5][6]
图的并行化表示 Parallel Graph Representations
图问题的并行化面临着重大的挑战: 数据驱动的计算、非结构化问题、局部性差和计算数据访问率高。[7][8] 用于并行架构的图表示在面对这些挑战时扮演着重要的角色。选择的表示方式不当可能会增加不必要的算法连接代价,从而降低算法的可扩展性。接下来的段落中,我们将着重探讨共享和分布式的内存架构。
在共享内存模型下,之所以用于并行处理的图表示与顺序处理的方式相同,[9]是因为对图表示的并行只读访问(例如:邻接表)是共享内存的有效方法。
分布式存储 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 必须是可识别的。在分布式图算法的计算过程中,沿着这些边传递信息意味着连接通信。[9]
图的划分需要仔细地进行——在低效率连接和大小划分之间有一个权衡。[10]但是图的划分是一个NP-难问题 NP-Hard Problem,因此计算它们是不可行的。不过,我们可以使用以下启发式。
1D 分区:每个处理器都会得到 [math]\displaystyle{ n/p }[/math] 顶点和相应的外边。这可以理解为按行或按列对邻接矩阵进行展开。对于在这种表示形式上运行的算法,需要一个 All-to-All 连接步骤以及 [math]\displaystyle{ mathcal{o}(m) }[/math] 消息缓冲区大小,因为每个 PE 可能具有相对于其他 PE 的输出边。[11]
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] 的邻接矩阵。这可以可视化为矩阵中的棋盘格模式。[11]因此,每个处理单元只能在同一行和列中具有 PE 的输出边。这将每个 PE 的通信伙伴的数量限制为[math]\displaystyle{ p = p_r \times p_c }[/math]可能伙伴中的 [math]\displaystyle{ p_r + p_c - 1 }[/math]个。
参见
- 图的遍历 Graph traversal 用于图遍历的策略
- 图数据库 Graph database 用于图(数据结构)的持久性
- 图重构 Graph rewriting 用于基于规则的图形转换(图数据结构)
- 画图软件 Graph drawing software 用于绘制图形的软件、系统和系统提供商
参考文献
- ↑ 1.0 1.1 See, e.g. Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see Mehlhorn, K.; Näher, S. (1999), "Chapter 6: Graphs and their data structures", LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, pp. 240–282.
- ↑ Cormen et al. (2001), pp. 528–529; Goodrich & Tamassia (2015), pp. 361-362.
- ↑ Cormen et al. (2001), pp. 529–530; Goodrich & Tamassia (2015), p. 363..
- ↑ Cormen et al. (2001), Exercise 22.1-7, p. 531.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.1: Representations of graphs", Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, pp. 527–531, ISBN 0-262-03293-7.
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 13.1: Graph terminology and representations", Algorithm Design and Applications, Wiley, pp. 355–364.
- ↑ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (January 2013) (in en). Graph Partitioning and Graph Clustering. Contemporary Mathematics. 588. American Mathematical Society. doi:10.1090/conm/588/11709. ISBN 978-0-8218-9038-7. http://www.ams.org/conm/588/.
- ↑ LUMSDAINE, ANDREW; GREGOR, DOUGLAS; HENDRICKSON, BRUCE; BERRY, JONATHAN (March 2007). "CHALLENGES IN PARALLEL GRAPH PROCESSING". Parallel Processing Letters. 17 (01): 5–20. doi:10.1142/s0129626407002843. ISSN 0129-6264.
- ↑ 9.0 9.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019) (in en). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer International Publishing. ISBN 978-3-030-25208-3. https://www.springer.com/gp/book/9783030252083.
- ↑ "Parallel Processing of Graphs" (PDF).
{{cite web}}
: CS1 maint: url-status (link) - ↑ 11.0 11.1 "Parallel breadth-first search on distributed memory systems | Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis". dl.acm.org (in English). doi:10.1145/2063384.2063471. Retrieved 2020-02-06.
其他链接
- 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.
本中文词条由923397935翻译,CecileLi审校,薄荷欢迎在讨论页面留言。
本词条内容源自公开资料,遵守 CC3.0协议。