图(抽象数据类型)

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

在计算机科学中,图是一种抽象的数据类型,用来展现数学中图论领域中的无向图 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).
  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翻译,CecileLiLux Cicero审校,薄荷欢迎在讨论页面留言。

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