1,564
个编辑
更改
跳到导航
跳到搜索
Moved page from wikipedia:en:Graph (abstract data type) (history)
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
[[File:Directed.svg|160px|thumb|A [[directed graph]] with three [[Vertex (graph theory)|vertices]] (blue circles) and three [[Edge (graph theory)|edges]] (black arrows).]]
A [[directed graph with three vertices (blue circles) and three edges (black arrows).]]
一个[有三个顶点(蓝色圆圈)和三条边(黑色箭头)的有向图]
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.
在计算机科学中，图是一种抽象的数据类型，用来实现数学中图论领域中的无向图和有向图的概念。
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.
一个图的数据结构由一个有限的(也可能是可变的)顶点集(也称为节点或点) ，以及一组无向图的无序顶点对或有向图的有序对组成。这些对称为边(也称为链接或直线) ，对于有向图，也称为箭头。顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。
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''.
Structures that associate values to the edges usually also provide:<ref name="gt-ops"/>
Structures that associate values to the edges usually also provide:
将值关联到边的结构通常还提供:
* <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''): sets the value associated with the edge (''x'', ''y'') to ''v''.
==Representations==
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
邻接表
: 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.
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
邻接矩阵
: 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.
一个二维矩阵，其中行表示源顶点，列表示目标顶点。关于边和顶点的数据必须存储在外部。只有一个边的开销可以存储在每对顶点之间。
; [[Incidence matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p. 531.</ref>
Incidence matrix
关联矩阵
: 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.
一个二维布尔矩阵，其中行表示顶点，列表示边。条目指示行上的顶点是否与列上的边相关联。
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 ∞.
下表给出了在图上执行各种操作的时间复杂度，对于每个表示，用 | v | 顶点数和 | e | 边数。在矩阵表示中，条目对跟随边的代价进行编码。假定不存在的边的代价为∞。
{| class="wikitable"
{| class="wikitable"
{ | class = “ wikitable”
|-
|-
|-
!
!
!
! scope="col" | Adjacency list
! scope="col" | Adjacency list
!“ col” | 邻接表
! scope="col" | Adjacency matrix
! scope="col" | Adjacency matrix
!范围 = “ col” | 邻接矩阵
! scope="col" | Incidence matrix
! scope="col" | Incidence matrix
!范围 = “ col” | 关联矩阵
|-
|-
|-
! scope="row" {{rh2|align=left}} | Store graph
! scope="row" | Store graph
!Scope = “ row” | Store graph
| <math>O(|V|+|E|)</math>
| <math>O(|V|+|E|)</math>
(| v | + | e |)
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| < math > o (| v | ^ 2)
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Add vertex
! scope="row" | Add vertex
!Scope = “ row” | Add vertex
| <math>O(1)</math>
| <math>O(1)</math>
| < math > o (1) </math >
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| < math > o (| v | ^ 2)
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Add edge
! 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(1)</math>
| < math > o (1) </math >
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Remove vertex
! scope="row" | Remove vertex
!Scope = “ row” | 删除顶点
| <math>O(|E|)</math>
| <math>O(|E|)</math>
| < math > o (| e |)
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| < math > o (| v | ^ 2)
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Remove edge
! scope="row" | Remove edge
!Scope = “ row” | Remove edge
| <math>O(|V|)</math>
| <math>O(|V|)</math>
| < math > o (| v |) </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>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Are vertices ''x'' and ''y'' adjacent (assuming that their storage positions are known)?
! 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 (| v |) </math >
| <math>O(1)</math>
| <math>O(1)</math>
| < math > o (1) </math >
| <math>O(|E|)</math>
| <math>O(|E|)</math>
| < math > o (| e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Remarks
! 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, 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.
邻接表通常是首选的，因为它们能有效地表示稀疏图。如果图是稠密的，那么邻接矩阵是首选的，即边的数目 | e | 接近于顶点的平方数，| v | < sup > 2 </sup > ，或者如果有一条边连接两个顶点，那么必须能够快速查找。
== Parallel Graph Representations ==
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 ===
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.
在共享内存模型的情况下，用于并行处理的图表示与顺序处理相同，因为对图表示的并行只读访问(例如:。邻接表)是共享内存的有效方法。
=== Distributed 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 > v0，dots，v { p-1} </math > 。这里，< math > p </math > 是可用处理元素(PE)的数量。然后，顶点集合分区被分配到具有匹配索引的 pe 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着通信。
[[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.
图的划分需要仔细地进行——在低通信和甚至大小划分之间有一个权衡。但是图的划分是一个 np 难问题，因此计算它们是不可行的。相反，使用以下启发式。
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 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.
</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 > 可能的伙伴。
==See also==
* [[Graph traversal]] for graph walking strategies
* [[Graph database]] for graph (data structure) persistency
* [[Graph rewriting]] for rule based transformations of graphs (graph data structures)
* [[Graph drawing software]] for software, systems, and providers of systems for drawing graphs
==References==
{{reflist}}
==External links==
{{Commons category}}
*[http://www.boost.org/libs/graph Boost Graph Library: a powerful C++ graph library] s.a. [[Boost (C++ libraries)]]
*[https://networkx.github.com/ Networkx: a Python graph library]
*[http://www.graphmatcher.com GraphMatcher] a java program to align directed/undirected graphs.
*[http://graphblas.org GraphBLAS] A specification for a library interface for operations on graphs, with a particular focus on sparse graphs.
{{Graph representations}}
{{Data structures}}
{{DEFAULTSORT:Graph (Abstract Data Type)}}
[[Category:Graph theory]]
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>
[[Category:待整理页面]]
[[File:Directed.svg|160px|thumb|A [[directed graph]] with three [[Vertex (graph theory)|vertices]] (blue circles) and three [[Edge (graph theory)|edges]] (black arrows).]]
A [[directed graph with three vertices (blue circles) and three edges (black arrows).]]
一个[有三个顶点(蓝色圆圈)和三条边(黑色箭头)的有向图]
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.
在计算机科学中，图是一种抽象的数据类型，用来实现数学中图论领域中的无向图和有向图的概念。
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.
一个图的数据结构由一个有限的(也可能是可变的)顶点集(也称为节点或点) ，以及一组无向图的无序顶点对或有向图的有序对组成。这些对称为边(也称为链接或直线) ，对于有向图，也称为箭头。顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。
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''.
Structures that associate values to the edges usually also provide:<ref name="gt-ops"/>
Structures that associate values to the edges usually also provide:
将值关联到边的结构通常还提供:
* <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''): sets the value associated with the edge (''x'', ''y'') to ''v''.
==Representations==
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
邻接表
: 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.
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
邻接矩阵
: 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.
一个二维矩阵，其中行表示源顶点，列表示目标顶点。关于边和顶点的数据必须存储在外部。只有一个边的开销可以存储在每对顶点之间。
; [[Incidence matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p. 531.</ref>
Incidence matrix
关联矩阵
: 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.
一个二维布尔矩阵，其中行表示顶点，列表示边。条目指示行上的顶点是否与列上的边相关联。
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 ∞.
下表给出了在图上执行各种操作的时间复杂度，对于每个表示，用 | v | 顶点数和 | e | 边数。在矩阵表示中，条目对跟随边的代价进行编码。假定不存在的边的代价为∞。
{| class="wikitable"
{| class="wikitable"
{ | class = “ wikitable”
|-
|-
|-
!
!
!
! scope="col" | Adjacency list
! scope="col" | Adjacency list
!“ col” | 邻接表
! scope="col" | Adjacency matrix
! scope="col" | Adjacency matrix
!范围 = “ col” | 邻接矩阵
! scope="col" | Incidence matrix
! scope="col" | Incidence matrix
!范围 = “ col” | 关联矩阵
|-
|-
|-
! scope="row" {{rh2|align=left}} | Store graph
! scope="row" | Store graph
!Scope = “ row” | Store graph
| <math>O(|V|+|E|)</math>
| <math>O(|V|+|E|)</math>
(| v | + | e |)
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| < math > o (| v | ^ 2)
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Add vertex
! scope="row" | Add vertex
!Scope = “ row” | Add vertex
| <math>O(1)</math>
| <math>O(1)</math>
| < math > o (1) </math >
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| < math > o (| v | ^ 2)
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Add edge
! 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(1)</math>
| < math > o (1) </math >
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Remove vertex
! scope="row" | Remove vertex
!Scope = “ row” | 删除顶点
| <math>O(|E|)</math>
| <math>O(|E|)</math>
| < math > o (| e |)
| <math>O(|V|^2)</math>
| <math>O(|V|^2)</math>
| < math > o (| v | ^ 2)
| <math>O(|V|\cdot|E|)</math>
| <math>O(|V|\cdot|E|)</math>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Remove edge
! scope="row" | Remove edge
!Scope = “ row” | Remove edge
| <math>O(|V|)</math>
| <math>O(|V|)</math>
| < math > o (| v |) </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>
| < math > o (| v | cdot | e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Are vertices ''x'' and ''y'' adjacent (assuming that their storage positions are known)?
! 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 (| v |) </math >
| <math>O(1)</math>
| <math>O(1)</math>
| < math > o (1) </math >
| <math>O(|E|)</math>
| <math>O(|E|)</math>
| < math > o (| e |)
|-
|-
|-
! scope="row" {{rh2|align=left}} | Remarks
! 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, 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.
邻接表通常是首选的，因为它们能有效地表示稀疏图。如果图是稠密的，那么邻接矩阵是首选的，即边的数目 | e | 接近于顶点的平方数，| v | < sup > 2 </sup > ，或者如果有一条边连接两个顶点，那么必须能够快速查找。
== Parallel Graph Representations ==
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 ===
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.
在共享内存模型的情况下，用于并行处理的图表示与顺序处理相同，因为对图表示的并行只读访问(例如:。邻接表)是共享内存的有效方法。
=== Distributed 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 > v0，dots，v { p-1} </math > 。这里，< math > p </math > 是可用处理元素(PE)的数量。然后，顶点集合分区被分配到具有匹配索引的 pe 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着通信。
[[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.
图的划分需要仔细地进行——在低通信和甚至大小划分之间有一个权衡。但是图的划分是一个 np 难问题，因此计算它们是不可行的。相反，使用以下启发式。
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 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.
</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 > 可能的伙伴。
==See also==
* [[Graph traversal]] for graph walking strategies
* [[Graph database]] for graph (data structure) persistency
* [[Graph rewriting]] for rule based transformations of graphs (graph data structures)
* [[Graph drawing software]] for software, systems, and providers of systems for drawing graphs
==References==
{{reflist}}
==External links==
{{Commons category}}
*[http://www.boost.org/libs/graph Boost Graph Library: a powerful C++ graph library] s.a. [[Boost (C++ libraries)]]
*[https://networkx.github.com/ Networkx: a Python graph library]
*[http://www.graphmatcher.com GraphMatcher] a java program to align directed/undirected graphs.
*[http://graphblas.org GraphBLAS] A specification for a library interface for operations on graphs, with a particular focus on sparse graphs.
{{Graph representations}}
{{Data structures}}
{{DEFAULTSORT:Graph (Abstract Data Type)}}
[[Category:Graph theory]]
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>
[[Category:待整理页面]]