7,129
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − '''粗体文字''' --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）在篇首写下 本词条由[[用户名]]初步翻译<br>+ − − 此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。 − 于2020.11.19再次审校，若有遗漏敬请谅解。 − + − 图1：A [[directed graph]] with three [[Vertex (graph theory)|vertices]] (blue circles) and three [[Edge (graph theory)|edges]] (black arrows).<br> − 一个有三个蓝色圆圈（点（'''<font color="#ff8000">图论 Graph Theory</font>'''）/顶点）和三条黑色箭头的边（边（图论）的有向图。 − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）注意图的格式 转行写[图1： 英文加翻译内容] − A [[directed graph with three vertices (blue circles) and three edges (black arrows).]] + − 一个有三个顶点(蓝色圆圈)和三条边(黑色箭头)的'''<font color="#ff8000">有向图 Directed Graph</font>'''。 + − In [[computer science]], a '''graph''' is an [[abstract data type]] that is meant to implement the [[Graph (discrete mathematics)|undirected graph]] and [[directed graph]] concepts from the field of [[graph theory]] within [[mathematics]].+ − In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics. − 在计算机科学中，图是一种抽象的数据类型，用来展现数学中图论领域中的'''<font color="#ff8000">无向图 Undirected Graph</font>'''和'''<font color="#ff8000">有向图 Directed Graph</font>'''的概念。 + + − A graph data structure consists of a finite (and possibly mutable) [[Set (computer science)|set]] of ''vertices'' (also called ''nodes'' or ''points''), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as ''edges'' (also called ''links'' or ''lines''), and for a directed graph are also known as ''arrows''. The vertices may be part of the graph structure, or may be external entities represented by integer indices or [[Reference (computer science)|references]].+ − A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as arrows. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.+ − 一个图的数据结构由一个有限的(也可能是可变的)'''<font color="#ff8000">顶点集 Set Of Vertices</font>'''(也称为节点或点) ，以及一组无向图的无序顶点对或有向图的有序顶点对组成。这些连线被称为边(也称为链接或直线) ，对于有向图，也称为箭头。顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。+ + + − A graph data structure may also associate to each edge some ''edge value'', such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).+ − A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).+ − 图形数据结构还可以为每条边关联一些边值，如符号标签或数字属性(成本、容量、长度等)。+ − + − ==Operations 操作方式== − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）章节名记得翻译 − The basic operations provided by a graph data structure ''G'' usually include:<ref name="gt-ops">See, e.g. {{harvtxt|Goodrich|Tamassia|2015}}, Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see {{citation|contribution=Chapter 6: Graphs and their data structures|pages=240–282|title=LEDA: A platform for combinatorial and geometric computing|first1=K.|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=S.|last2=Näher|publisher=Cambridge University Press|year=1999}}.</ref> − − The basic operations provided by a graph data structure G usually include: − − 图形''G'' 的数据结构提供的基本操作通常包括: − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）变量斜体 − * <code>adjacent</code>(''G'', ''x'', ''y''): tests whether there is an edge from the vertex ''x'' to the vertex ''y''; − − * <code>neighbors</code>(''G'', ''x''): lists all vertices ''y'' such that there is an edge from the vertex ''x'' to the vertex ''y''; − − * <code>add_vertex</code>(''G'', ''x''): adds the vertex ''x'', if it is not there; − − * <code>remove_vertex</code>(''G'', ''x''): removes the vertex ''x'', if it is there; − − * <code>add_edge</code>(''G'', ''x'', ''y''): adds the edge from the vertex ''x'' to the vertex ''y'', if it is not there; − − * <code>remove_edge</code>(''G'', ''x'', ''y''): removes the edge from the vertex ''x'' to the vertex ''y'', if it is there; − − * <code>get_vertex_value</code>(''G'', ''x''): returns the value associated with the vertex ''x''; − − * <code>set_vertex_value</code>(''G'', ''x'', ''v''): sets the value associated with the vertex ''x'' to ''v''. − − * <code>adjacent</code>(" G "， " x "， " y "):检验顶点" x "到顶点" y "是否有边; − − * <code>neighbors</code>(“G”，“x”):列出所有顶点“y”，使顶点“x”有一条边到顶点“y”; − − * <code> add_vertex > < /代码(“G”、“x”):添加顶点“x”,如果它是不存在的; − − * <code>remove_vertex</code>(" G "， " x "):删除顶点" x "(如果存在的话); − − * <code>add_edge</code>(" G "， " x "， " y "):将顶点" x "的边添加到顶点" y "(如果不存在的话); − − * <code>remove_edge</code>(" G "， " x "， " y "):将顶点" x "的边移到顶点" y "的边(如果存在的话); − − * <code>get_vertex_value</code>(" G "， " x "):返回与顶点" x "相关的值; − − * <code> set_vertex_value > </code>(“G”、“x”、“v”):设置顶点的值与“x”“v”。 − − Structures that associate values to the edges usually also provide:<ref name="gt-ops"/> − − Structures that associate values to the edges usually also provide: − − 将值关联到边的结构通常还提供: 第94行：
第45行： − + − − Different data structures for the representation of graphs are used in practice: − − Different data structures for the representation of graphs are used in practice: − 图表示的不同数据结构在实践中的使用:+ − ; [[Adjacency list]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 528–529; {{harvtxt|Goodrich|Tamassia|2015}}, pp. 361-362.</ref>+ − Adjacency list+ − '''<font color="#ff8000">邻接表 Adjacency List</font>'''+ − + − Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.+ − 顶点作为记录或存储对象，每个顶点存储一个相邻顶点列表。这种数据结构允许在顶点上存储额外的数据。如果边也被存储为对象，那么它就可以存储额外的数据，在这种情况下，每个顶点记录着它的关联边，每个边又存储它的关联顶点。+ − ; [[Adjacency matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 529–530; {{harvtxt|Goodrich|Tamassia|2015}}, p. 363.</ref> − − Adjacency matrix − − '''<font color="#ff8000">邻接矩阵 Adjacency Matrix</font>''' − − : A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices. − − A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices. − − 一个二维矩阵，其中行表示'''<font color="#ff8000">源顶点 Source Vertices</font>'''，列表示'''<font color="#ff8000">目标顶点 Destination Vertices</font>'''。关于边和顶点的数据必须存储在外部。只有一条边时它可以被存储在每对顶点之间。 − − ; [[Incidence matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p. 531.</ref> − − Incidence matrix − − '''<font color="#ff8000">关联矩阵 Incidence Matrix</font>''' − − : A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column. − − A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column. − − 一个二维布尔矩阵，其中行表示顶点，列表示边。'''<font color="#32CD32">矩阵的条目值</font>'''The entries 表明行上的顶点是否与列上的边是相关联。 − --信白 该句存疑.翻译成条目值感觉不合适 − − − − The following table gives the [[time complexity]] cost of performing various operations on graphs, for each of these representations, with |''V'' | the number of vertices and |''E'' | the number of edges.{{Citation needed|reason=Reliable source needed for the entire table below.|date=November 2011}} In the matrix representations, the entries encode the cost of following an edge. The cost of edges that are not present are assumed to be ∞. − − The following table gives the time complexity cost of performing various operations on graphs, for each of these representations, with |V | the number of vertices and |E | the number of edges. In the matrix representations, the entries encode the cost of following an edge. The cost of edges that are not present are assumed to be ∞. − − 下表给出了在图上执行各种操作的'''<font color="#ff8000">时间复杂度 Time Complexity</font>'''，对于每个表达式，用 | <big>V</big> | 顶点数和 | <big>E</big> | 边数。在矩阵表示中，'''<font color="#32CD32">条目值</font>'''the entries跟随边的代价进行编码。假定不存在的边的值为∞。 + − + − {| class="wikitable"+ − + − { | class = “ wikitable”+ − − |- − − |- − − |- − − ! − − ! − − ! − − ! scope="col" | Adjacency list − − − − !“ col” | 邻接表 − − ! scope="col" | Adjacency matrix − − − − !范围 = “ col” | 邻接矩阵 − − − − ! scope="col" | Incidence matrix − − !范围 = “ col” | 关联矩阵 − − |- − − |- − − |- − − − − ! scope="row" | Store graph − − !Scope = “ row” | Store graph − − | <math>O(|V|+|E|)</math> − − − (| v | + | e |) − − | <math>O(|V|^2)</math> − − − | < math > o (| v | ^ 2) − − | <math>O(|V|\cdot|E|)</math> − − − | < math > o (| v | cdot | e |) − − |- − − + − |- − − − − ! scope="row" | Add vertex − − !Scope = “ row” | Add vertex − − | <math>O(1)</math> − − − | < math > o (1) </math > − − | <math>O(|V|^2)</math> − − − | < math > o (| v | ^ 2) − − − | <math>O(|V|\cdot|E|)</math> − − | < math > o (| v | cdot | e |) − − |- − − |- − − + − − − ! scope="row" | Add edge − − !Scope = “ row” | Add edge − − | <math>O(1)</math> − − − | < math > o (1) </math > − − − | <math>O(1)</math> − − | < math > o (1) </math > − − − | <math>O(|V|\cdot|E|)</math> − − | < math > o (| v | cdot | e |) − − |- − − |- − − + − − − ! scope="row" | Remove vertex − − !Scope = “ row” | 删除顶点 − − | <math>O(|E|)</math> − − − | < math > o (| e |) − − | <math>O(|V|^2)</math> − − − | < math > o (| v | ^ 2) − − | <math>O(|V|\cdot|E|)</math> − − − | < math > o (| v | cdot | e |) − − |- − − + − |- − − − − ! scope="row" | Remove edge − − !Scope = “ row” | Remove edge − − | <math>O(|V|)</math> − − − | < math > o (| v |) </math > − − | <math>O(1)</math> − − − | < math > o (1) </math > − − − | <math>O(|V|\cdot|E|)</math> − − | < math > o (| v | cdot | e |) − − |- − − |- − − + − − − ! scope="row" | Are vertices x and y adjacent (assuming that their storage positions are known)? − − !Scope = “ row” | 顶点 x 和 y 是否相邻(假设它们的存储位置已知) ？ − − | <math>O(|V|)</math> − − − | < math > o (| v |) </math > − − − | <math>O(1)</math> − − | < math > o (1) </math > − − − | <math>O(|E|)</math> − − | < math > o (| e |) − − |- − − |- − − + − + − − ! scope="row" | Remarks − − !Scope = “ row” | 备注 − − | Slow to remove vertices and edges, because it needs to find all vertices or edges − − | Slow to remove vertices and edges, because it needs to find all vertices or edges − − 因为移除顶点和边需要找到所有的顶点或边，所以它的进行速度很慢， − − − − | Slow to add or remove vertices, because matrix must be resized/copied − − − | Slow to add or remove vertices and edges, because matrix must be resized/copied − − | Slow to add or remove vertices and edges, because matrix must be resized/copied − − − |} − − |} − + + − Adjacency lists are generally preferred because they efficiently represent [[sparse graph]]s. An adjacency matrix is preferred if the graph is dense, that is the number of edges |''E'' | is close to the number of vertices squared, |''V'' |<sup>2</sup>, or if one must be able to quickly look up if there is an edge connecting two vertices.<ref name="clrs">{{citation |authorlink=Thomas H. Cormen |first=Thomas H. |last=Cormen |authorlink2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |authorlink3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |authorlink4=Clifford Stein |first4=Clifford |last4=Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |chapter=Section 22.1: Representations of graphs |pages=527–531 }}.</ref><ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|contribution=Section 13.1: Graph terminology and representations|pages=355–364}}.</ref>+ − − Adjacency lists are generally preferred because they efficiently represent sparse graphs. An adjacency matrix is preferred if the graph is dense, that is the number of edges |E | is close to the number of vertices squared, |V |<sup>2</sup>, or if one must be able to quickly look up if there is an edge connecting two vertices. − − 邻接表通常是首选的，因为它们能有效地表示'''<font color="#ff8000">稀疏图 Sparse Graph</font>'''。如果图是'''<font color="#ff8000">稠密图 Dense Graph</font>'''的，那么邻接矩阵是首选的，即边的数目 |<big>E</big>| 接近于顶点的平方数，|<big>V</big>|<sup>2</sup> ，或者说如果有一条边连接两个顶点，那么所选取的数据结构必须满足可以快速查找到数据。 − − == Parallel Graph Representations 图的并行化表示== − <br> − − The parallelization of graph problems faces significant challenges: Data-driven computations, unstructured problems, poor locality and high data access to computation ratio.<ref name=":1">{{Cite book|last=Bader|first=David|url=http://www.ams.org/conm/588/|title=Graph Partitioning and Graph Clustering|last2=Meyerhenke|first2=Henning|last3=Sanders|first3=Peter|last4=Wagner|first4=Dorothea|date=January 2013|publisher=American Mathematical Society|isbn=978-0-8218-9038-7|series=Contemporary Mathematics|volume=588|language=en|doi=10.1090/conm/588/11709}}</ref><ref>{{Cite journal|last=LUMSDAINE|first=ANDREW|last2=GREGOR|first2=DOUGLAS|last3=HENDRICKSON|first3=BRUCE|last4=BERRY|first4=JONATHAN|date=March 2007|title=CHALLENGES IN PARALLEL GRAPH PROCESSING|url=http://dx.doi.org/10.1142/s0129626407002843|journal=Parallel Processing Letters|volume=17|issue=01|pages=5–20|doi=10.1142/s0129626407002843|issn=0129-6264}}</ref> The graph representation used for parallel architectures plays a significant role in facing those challenges. Poorly chosen representations may unnecessarily drive up the communication cost of the algorithm, which will decrease its [[scalability]]. In the following, shared and distributed memory architectures are considered. − − The parallelization of graph problems faces significant challenges: Data-driven computations, unstructured problems, poor locality and high data access to computation ratio. The graph representation used for parallel architectures plays a significant role in facing those challenges. Poorly chosen representations may unnecessarily drive up the communication cost of the algorithm, which will decrease its scalability. In the following, shared and distributed memory architectures are considered. − − 图问题的并行化面临着重大的挑战: 数据驱动的计算、非结构化问题、局部性差和计算数据访问率高。用于并行架构的图表示在面对这些挑战时扮演着重要的角色。选择的表示方式不当可能会增加不必要的算法连接代价，从而降低算法的可扩展性。接下来的段落中，我们将着重探讨共享和分布式的内存架构。 − − − === Shared memory 共享内存=== − <br> − In the case of a [[shared memory]] model, the graph representations used for parallel processing are the same as in the sequential case,<ref name=":0">{{Cite book|last=Sanders|first=Peter|url=https://www.springer.com/gp/book/9783030252083|title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer International Publishing|isbn=978-3-030-25208-3|language=en}}</ref> since parallel read-only access to the graph representation (e.g. an [[adjacency list]]) is efficient in shared memory. − In the case of a shared memory model, the graph representations used for parallel processing are the same as in the sequential case, since parallel read-only access to the graph representation (e.g. an adjacency list) is efficient in shared memory.+ − 在共享内存模型下，之所以用于并行处理的图表示与顺序处理的方式相同，是因为对图表示的并行只读访问(例如:邻接表)是共享内存的有效方法。+ − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）通读一遍 注意多余符号的问题(例如:。邻接表) − + − In the [[distributed memory]] model, the usual approach is to [[Graph partition|partition]] the vertex set <math>V</math> of the graph into <math>p</math> sets <math>V_0, \dots, V_{p-1}</math>. Here, <math>p</math> is the amount of available processing elements (PE). The vertex set partitions are then distributed to the PEs with matching index, additionally to the corresponding edges. Every PE has its own [[Subgraph (graph theory)|subgraph]] representation, where edges with an endpoint in another partition require special attention. For standard communication interfaces like [[Message Passing Interface|MPI]], the ID of the PE owning the other endpoint has to be identifiable. During computation in a distributed graph algorithms, passing information along these edges implies communication.<ref name=":0" /> − − In the distributed memory model, the usual approach is to partition the vertex set <math>V</math> of the graph into <math>p</math> sets <math>V_0, \dots, V_{p-1}</math>. Here, <math>p</math> is the amount of available processing elements (PE). The vertex set partitions are then distributed to the PEs with matching index, additionally to the corresponding edges. Every PE has its own subgraph representation, where edges with an endpoint in another partition require special attention. For standard communication interfaces like MPI, the ID of the PE owning the other endpoint has to be identifiable. During computation in a distributed graph algorithms, passing information along these edges implies communication. − − 在分布式存储模型中，常用的方法是将图的顶点集合<math>V</math> 分解为<math>P</math> 集合 <math> Vo,…,V{ p-1}</math> 。这里，<math>p</math> 是可用处理元素(PE)的数量。然后，顶点集合分区被分配到具有匹配索引的 PE 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着连接通信。 − − --信白该句存疑Vo到Vp-1没写好 − − − [[Graph partition|Partitioning the graph]] needs to be done carefully - there is a trade-off between low communication and even size partitioning<ref>{{Cite web|url=https://www.graphengine.io/downloads/papers/ParallelProcessingOfGraphs.pdf|title=Parallel Processing of Graphs|last=|first=|date=|website=|url-status=live|archive-url=|archive-date=|access-date=}}</ref> But partitioning a graph is a NP-hard problem, so it is not feasible to calculate them. Instead, the following heuristics are used. − Partitioning the graph needs to be done carefully - there is a trade-off between low communication and even size partitioning But partitioning a graph is a NP-hard problem, so it is not feasible to calculate them. Instead, the following heuristics are used.+ − 图的划分需要仔细地进行——在低效率连接和大小划分之间有一个权衡。但是图的划分是一个'''<font color="#ff8000"><big>NP</big>艰难的问题 NP-Hard Problem</font>，因此计算它们是不可行的。不过，我们可以使用以下启发式。 + − + − 1D partitioning: Every processor gets <math>n/p</math> vertices and the corresponding outgoing edges. This can be understood as a row-wise or column-wise decomposition of the adjacency matrix. For algorithms operating on this representation, this requires an All-to-All communication step as well as <math>\mathcal{O}(m)</math> message buffer sizes, as each PE potentially has outgoing edges to every other PE. − 1D 分区: 每个处理器都会得到 <math>n/p</math> 顶点和相应的外边。这可以理解为按行或按列对邻接矩阵进行展开。对于在这种表示形式上运行的算法，需要一个 All-to-All 连接步骤以及 <math> mathcal{o}(m)</math> 消息缓冲区大小，因为每个 PE 可能具有相对于其他 PE 的输出边。+ + − 2D partitioning: Every processor gets a submatrix of the adjacency matrix. Assume the processors are aligned in a rectangle <math>p = p_r \times p_c</math>, where <math>p_r+ + + + − 2D partitioning: Every processor gets a submatrix of the adjacency matrix. Assume the processors are aligned in a rectangle <math>p = p_r \times p_c</math>, where <math>p_r − 2 d 分区: 每个处理器都有一个邻接矩阵的子矩阵。假设处理器在一个矩形 <math>p = p_r 乘以 p_c</math> 中对齐，其中 + − − <math>p_r</math>and<math>p_c</math>and<math>p_c[/math ]和[ math ]</math> are the amount of processing elements in each row and column, respectively. Then each processor gets a [[submatrix]] of the adjacency matrix of dimension <math>(n/p_r)\times(n/p_c)</math>. This can be visualized as a [[checkerboard]] pattern in a matrix.<ref name=":2" /> Therefore, each processing unit can only have outgoing edges to PEs in the same row and column. This bounds the amount of communication partners for each PE to <math>p_r + p_c - 1</math> out of <math>p = p_r \times p_c</math> possible ones. − − </math> are the amount of processing elements in each row and column, respectively. Then each processor gets a submatrix of the adjacency matrix of dimension <math>(n/p_r)\times(n/p_c)</math>. This can be visualized as a checkerboard pattern in a matrix. Therefore, each processing unit can only have outgoing edges to PEs in the same row and column. This bounds the amount of communication partners for each PE to <math>p_r + p_c - 1</math> out of <math>p = p_r \times p_c</math> possible ones. − − '''<font color="#32CD32"></math > 是每行和每列中处理元素的数量。然后每个处理器得到维数 <math> (n/p_r)乘以(n/p_c)</math> 的邻接矩阵。这可以可视化为矩阵中的棋盘格模式。因此，每个处理单元只能在同一行和列中具有 PE 的输出边。这将每个 PE 的通信伙伴的数量限制为 <math> p_r + p_c-1 </math> 出 <math> p = p_r 乘以 p_c </math> 可能的伙伴。</font>'''</math> are the amount of processing elements in each row and column, respectively. Then each processor gets a submatrix of the adjacency matrix of dimension <math>(n/p_r)\times(n/p_c)</math>. This can be visualized as a checkerboard pattern in a matrix. Therefore, each processing unit can only have outgoing edges to PEs in the same row and column. This bounds the amount of communication partners for each PE to <math>p_r + p_c - 1</math> out of <math>p = p_r \times p_c</math> possible ones. − --信白该句存疑，</math>是代码吗？这块儿没明白怎么搞 − − ==See also 另请参见== − − * [[Graph traversal]] for graph walking strategies − '''<font color="#ff8000">图的遍历 Graph Traversal</font>'''用于图遍历的策略 − * [[Graph database]] for graph (data structure) persistency − '''<font color="#ff8000">图数据库 Graph Database</font>'''用于图（数据结构）的持久性 − * [[Graph rewriting]] for rule based transformations of graphs (graph data structures) − '''<font color="#ff8000">图重构 Graph Rewriting</font>'''用于基于规则的图形转换（图数据结构） − * [[Graph drawing software]] for software, systems, and providers of systems for drawing graphs − '''<font color="#ff8000">画图软件 Graph Drawing Software</font>'''用于绘制图形的软件、系统和系统提供商 − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）see also记得翻译完全 − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）可以看看之前发的链接“集智百科翻译团队新手指南”按着上面的要求再核对一下 比如专业名词标橙 疑难句标绿 − − ==References 参考文献== − + 第504行：
第161行： − {{Graph representations}}+ − − {{Data structures}} − − − − {{DEFAULTSORT:Graph (Abstract Data Type)}} − − − − Category:Graph theory − − 范畴: 图论 − − [[Category:Graph data structures| ]] − − [[Category:Abstract data types]] − − Category:Abstract data types − − 类别: 抽象数据类型 − − [[Category:Graphs]] − − Category:Graphs − − 分类: 图表 − − [[Category:Hypergraphs]] − − Category:Hypergraphs − − 分类: 超图 − <noinclude>+ − <small>This page was moved from [[wikipedia:en:Graph (abstract data type)]]. Its edit history can be viewed at [[图（抽象数据类型）/edithistory]]</small></noinclude>+ − +
无编辑摘要
本词条由923397935初步翻译
本词条由923397935初步翻译<br>
由CecileLi初步审校
由CecileLi初步审校
“表示方法”一目下表格中的部分文字没有翻译
“表示方法”一目下表格中的部分文字没有翻译
[[File:Directed.svg|160px|thumb|A [[directed graph]] with three [[Vertex (graph theory)|vertices]] (blue circles) and three [[Edge (graph theory)|edges]] (black arrows).]]<br>
[[File:Directed.svg|160px|thumb|一个有三个顶点（蓝色圆圈）和三条边（黑色箭头）的有向图。]]<br>
在计算机科学中，图是一种抽象的数据类型，用来展现数学中图论领域中的'''<font color="#ff8000">无向图 undirected graph</font>'''和'''<font color="#ff8000">有向图 directed graph</font>'''的概念。
一个图的数据结构由一组有限的（也可能是可变的）'''顶点 vertices'''（也称为节点 nodes或点 points） ，以及一组无向图的无序顶点对或有向图的有序顶点对组成。这些连线被称为'''边 edges'''（也称为链接 links或直线 lines），对于有向图，也称为'''箭头 arrows'''。顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。
图形数据结构还可以为每条边关联一些'''边值 edge value'''，如符号标签或数字属性（成本、容量、长度等）。
==操作方式 Operations==
图形'' G ''的数据结构提供的基本操作通常包括：<ref name="gt-ops">See, e.g. {{harvtxt|Goodrich|Tamassia|2015}}, Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see {{citation|contribution=Chapter 6: Graphs and their data structures|pages=240–282|title=LEDA: A platform for combinatorial and geometric computing|first1=K.|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=S.|last2=Näher|publisher=Cambridge University Press|year=1999}}.</ref>
* <code>adjacent</code>(''G'', ''x'', ''y''):检验顶点'' x ''到顶点'' y ''是否存在边；
* <code>neighbors</code>(''G'', ''x'')：列出所有顶点'' y ''，使顶点'' x ''有一条边到顶点'' y ''；
* <code>add_vertex</code>(''G'', ''x'')：添加新顶点'' x ''；
* <code>remove_vertex</code>(''G'', ''x'')：删除已有顶点'' x ''；
* <code>add_edge</code>(''G'', ''x'', ''y'')：添加一条连接顶点'' x ''和顶点'' y ''的边；
* <code>remove_edge</code>(''G'', ''x'', ''y'')：删除连接顶点'' x ''和顶点'' y ''的边;
* <code>get_vertex_value</code>(''G'', ''x'')：返回与顶点'' x ''相关的值;
* <code>set_vertex_value</code>(''G'', ''x'', ''v'')：设置顶点的值与'' x '''' v ''.
将值关联到边的结构通常还提供：<ref name="gt-ops"/>
* <code>get_edge_value</code>(''G'', ''x'', ''y''): returns the value associated with the edge (''x'', ''y'');
* <code>get_edge_value</code>(''G'', ''x'', ''y''): returns the value associated with the edge (''x'', ''y'');
* <code>set_edge_value</code>(''G'', ''x'', ''y'', ''v''): 连接点(''x'', ''y'') 到 ''v''的设置值.
* <code>set_edge_value</code>(''G'', ''x'', ''y'', ''v''): 连接点(''x'', ''y'') 到 ''v''的设置值.
==Representations 表示方法==
== 表示方法 Representations==
在实际应用中不同数据结构的图表示方法:
*[[邻接表 Adjacency list]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 528–529; {{harvtxt|Goodrich|Tamassia|2015}}, pp. 361-362.</ref>===
:顶点作为记录或存储对象，每个顶点存储一个相邻顶点列表。这种数据结构允许在顶点上存储额外的数据。如果边也被存储为对象，那么它就可以存储额外的数据，在这种情况下，每个顶点记录着它的关联边，每个边又存储它的关联顶点。
*[[邻接矩阵 Adjacency matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 529–530; {{harvtxt|Goodrich|Tamassia|2015}}, p. 363.</ref>
: Vertices are stored as records or objects, and every vertex stores a [[list (computing)|list]] of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.
:一个二维矩阵，其中行表示'''<font color="#ff8000">源顶点 Source Vertices</font>'''，列表示'''<font color="#ff8000">目标顶点 Destination Vertices</font>'''。关于边和顶点的数据必须存储在外部。只有一条边时它可以被存储在每对顶点之间。
*[[关联矩阵 Incidence matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p. 531.</ref>
: 一个二维布尔矩阵，其中行表示顶点，列表示边。'''<font color="#ff8000">矩阵的条目值 entries </font>'''表明行上的顶点是否与列上的边是相关联。
下表给出了在图上执行各种操作的'''<font color="#ff8000">时间复杂度 Time Complexity</font>'''，对于每个表达式，用 | '' V '' | 顶点数和 | '' E '' | 边数。在矩阵表示中，'''<font color="#32CD32">条目值</font>'''the entries跟随边的代价进行编码。假定不存在的边的值为∞。
{| class="wikitable"
{| class="wikitable"
! scope="col" | 邻接表
! scope="col" | 邻接矩阵
! scope="col" | 关联矩阵
! scope="row" {{rh2|align=left}} | 图的存储
! scope="col" | Adjacency list
! scope="col" | Adjacency matrix
! scope="col" | Incidence matrix
! scope="row" {{rh2|align=left}} | Store graph
| <math>O(|V|+|E|)</math>
| <math>O(|V|+|E|)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
|-
|-
! scope="row" {{rh2|align=left}} | 添加顶点
! scope="row" {{rh2|align=left}} | Add vertex
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
|-
|-
! scope="row" {{rh2|align=left}} | 添加边
! scope="row" {{rh2|align=left}} | Add edge
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
|-
|-
! scope="row" {{rh2|align=left}} | 删除顶点
! scope="row" {{rh2|align=left}} | Remove vertex
| <math>O(|E|)</math>
| <math>O(|E|)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
|-
|-
! scope="row" {{rh2|align=left}} | 删除边
! scope="row" {{rh2|align=left}} | Remove edge
| <math>O(|V|)</math>
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
|-
|-
! scope="row" {{rh2|align=left}} | 判断顶点 x 和 y 是否相邻(假设它们的存储位置已知)
! scope="row" {{rh2|align=left}} | Are vertices ''x'' and ''y'' adjacent (assuming that their storage positions are known)?
| <math>O(|V|)</math>
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(|E|)</math>
| <math>O(|E|)</math>
|-
|-
! scope="row" {{rh2|align=left}} | 备注
! scope="row" {{rh2|align=left}} | Remarks
| 因为顶点和边的删除操作需要找到所有的顶点或边，所以它的进行速度很慢，
| Slow to add or remove vertices, because matrix must be resized/copied
| 增加或删除顶点速度慢，因为矩阵必须调整大小/复制
| 增加或删除顶点速度慢，因为矩阵必须调整大小/复制
| 因为矩阵必须调整大小/或进行复制，所以增加或删除顶点和边时速度慢，
| 因为矩阵必须调整大小/或进行复制，所以增加或删除顶点和边时速度慢，
|}
|}
邻接表通常是首选的，因为它们能有效地表示'''<font color="#ff8000">稀疏图 Sparse Graph</font>'''。如果图是'''<font color="#ff8000">稠密图 Dense Graph</font>'''的，那么邻接矩阵是首选的，即边的数目 |'' E ''| 接近于顶点的平方数，|'' V ''|<sup>2</sup> ，或者说如果有一条边连接两个顶点，那么所选取的数据结构必须满足可以快速查找到数据。<ref name="clrs">{{citation |authorlink=Thomas H. Cormen |first=Thomas H. |last=Cormen |authorlink2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |authorlink3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |authorlink4=Clifford Stein |first4=Clifford |last4=Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |chapter=Section 22.1: Representations of graphs |pages=527–531 }}.</ref><ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|contribution=Section 13.1: Graph terminology and representations|pages=355–364}}.</ref>
== 图的并行化表示 Parallel Graph Representations==
图问题的并行化面临着重大的挑战: 数据驱动的计算、非结构化问题、局部性差和计算数据访问率高。<ref name=":1">{{Cite book|last=Bader|first=David|url=http://www.ams.org/conm/588/|title=Graph Partitioning and Graph Clustering|last2=Meyerhenke|first2=Henning|last3=Sanders|first3=Peter|last4=Wagner|first4=Dorothea|date=January 2013|publisher=American Mathematical Society|isbn=978-0-8218-9038-7|series=Contemporary Mathematics|volume=588|language=en|doi=10.1090/conm/588/11709}}</ref><ref>{{Cite journal|last=LUMSDAINE|first=ANDREW|last2=GREGOR|first2=DOUGLAS|last3=HENDRICKSON|first3=BRUCE|last4=BERRY|first4=JONATHAN|date=March 2007|title=CHALLENGES IN PARALLEL GRAPH PROCESSING|url=http://dx.doi.org/10.1142/s0129626407002843|journal=Parallel Processing Letters|volume=17|issue=01|pages=5–20|doi=10.1142/s0129626407002843|issn=0129-6264}}</ref> 用于并行架构的图表示在面对这些挑战时扮演着重要的角色。选择的表示方式不当可能会增加不必要的算法连接代价，从而降低算法的可扩展性。接下来的段落中，我们将着重探讨共享和分布式的内存架构。
===共享内存 Shared memory===
在共享内存模型下，之所以用于并行处理的图表示与顺序处理的方式相同，<ref name=":0">{{Cite book|last=Sanders|first=Peter|url=https://www.springer.com/gp/book/9783030252083|title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer International Publishing|isbn=978-3-030-25208-3|language=en}}</ref>是因为对图表示的并行只读访问(例如：邻接表)是共享内存的有效方法。
=== Distributed Memory 分布式存储===
=== 分布式存储 distributed memory===
<br>
<br>
在分布式存储模型中，常用的方法是将图的顶点集合<math>V</math> 分解为<math>p</math> 集合 <math> Vo,\dots,V{ p-1}</math> 。这里，<math>p</math> 是可用处理元素 processing elements（PE）的数量。然后，顶点集合分区被分配到具有匹配索引的 PE 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着连接通信。<ref name=":0" />
图的划分需要仔细地进行——在低效率连接和大小划分之间有一个权衡。<ref>{{Cite web|url=https://www.graphengine.io/downloads/papers/ParallelProcessingOfGraphs.pdf|title=Parallel Processing of Graphs|last=|first=|date=|website=|url-status=live|archive-url=|archive-date=|access-date=}}</ref>但是图的划分是一个'''NP-难问题 NP-Hard Problem'''，因此计算它们是不可行的。不过，我们可以使用以下启发式。
1D partitioning: Every processor gets <math>n/p</math> vertices and the corresponding outgoing edges. This can be understood as a row-wise or column-wise decomposition of the adjacency matrix. For algorithms operating on this representation, this requires an All-to-All communication step as well as <math>\mathcal{O}(m)</math> message buffer sizes, as each PE potentially has outgoing edges to every other PE.<ref name=":2">{{Cite web|url=https://dl.acm.org/doi/abs/10.1145/2063384.2063471|title=Parallel breadth-first search on distributed memory systems {{!}} Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis|website=dl.acm.org|language=EN|doi=10.1145/2063384.2063471|access-date=2020-02-06}}</ref>
1D 分区: 每个处理器都会得到 <math>n/p</math> 顶点和相应的外边。这可以理解为按行或按列对邻接矩阵进行展开。对于在这种表示形式上运行的算法，需要一个 All-to-All 连接步骤以及 <math> mathcal{o}(m)</math> 消息缓冲区大小，因为每个 PE 可能具有相对于其他 PE 的输出边。<ref name=":2">{{Cite web|url=https://dl.acm.org/doi/abs/10.1145/2063384.2063471|title=Parallel breadth-first search on distributed memory systems {{!}} Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis|website=dl.acm.org|language=EN|doi=10.1145/2063384.2063471|access-date=2020-02-06}}</ref>
2D分区: 每个处理器都有一个邻接矩阵的子矩阵。假设处理器在一个矩形<math>p = p_r \times p_c</math> 中对齐，其中 <math>p_r</math>和<math>p_c</math>是每行和每列中处理元素的数量。然后每个处理器得到维数<math>(n/p_r)\times(n/p_c)</math> 的邻接矩阵。这可以可视化为矩阵中的棋盘格模式。<ref name=":2" />因此，每个处理单元只能在同一行和列中具有 PE 的输出边。这将每个 PE 的通信伙伴的数量限制为 <math>p_r + p_c - 1</math> 出<math>p = p_r \times p_c</math>可能的伙伴
==参见==
* [[图的遍历 Graph traversal]] 用于图遍历的策略
* [[图数据库 Graph database]] 用于图（数据结构）的持久性
* [[图重构 Graph rewriting]] 用于基于规则的图形转换（图数据结构）
* [[画图软件 Graph drawing software]] 用于绘制图形的软件、系统和系统提供商
==参考文献==
{{reflist}}
{{reflist}}
==External links 外部链接==
==其他链接==
{{Commons category}}
{{Commons category}}
[[Category:图论]]
[[Category:Graph theory]]
[[Category:抽象数据类型 ]]
[[Category:图]]
[[Category:待整理页面]]
[[Category:超图]]