图（抽象数据类型）

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
一个有三个顶点（蓝色圆圈）和三条边（黑色箭头）的有向图。

在计算机科学中，图是一种抽象的数据类型，用来展现数学中图论领域中的无向图 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；
  • 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。

表示方法 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] 用于并行架构的图表示在面对这些挑战时扮演着重要的角色。选择的表示方式不当可能会增加不必要的算法连接代价，从而降低算法的可扩展性。接下来的段落中，我们将着重探讨共享和分布式的内存架构。


共享内存 Shared memory

在共享内存模型下，之所以用于并行处理的图表示与顺序处理的方式相同，[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]个。


参见


参考文献

  1. ↑ 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.
  2. ↑ Cormen et al. (2001), pp. 528–529; Goodrich & Tamassia (2015), pp. 361-362.
  3. ↑ Cormen et al. (2001), pp. 529–530; Goodrich & Tamassia (2015), p. 363..
  4. ↑ Cormen et al. (2001), Exercise 22.1-7, p. 531.
  5. ↑ 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.
  6. ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 13.1: Graph terminology and representations", Algorithm Design and Applications, Wiley, pp. 355–364.
  7. ↑ 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/. 
  8. ↑ 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. ↑ 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. 
  10. ↑ "Parallel Processing of Graphs" (PDF).{{cite web}}: CS1 maint: url-status (link)
  11. ↑ 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.

编者推荐

ER随机图模型

随机图（random graph），顾名思义，是由随机过程产生的图，具有不确定性。这一理论处于图论和概率论的交叉地带，主要研究经典随机图的性质。


图网络解决优化问题

图神经网络是深度学习领域的前沿热点议题，尤其是图网络（GraphNetworks）提出以来，深度学习有了实现因果推理的潜力。为了持续追踪相关领域的前沿进展，集智俱乐部联合北师大系统科学学院张江课题组，组织了以图网络为主题的线上读书会，研讨最新论文，孕育研究思路。本系列课程为图网络论文解读活动“图网络解决优化问题”篇。


系统讲解知识图谱——从建模到应用

本系列课程中，我们将围绕知识图谱，从知识建模、知识获取、知识管理到知识赋能整个生命周期，进行系统讲解。


本中文词条由923397935翻译，CecileLi、Lux Cicero审校，薄荷欢迎在讨论页面留言。

本词条内容源自公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=图（抽象数据类型）&oldid=21055”