更改

[[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|A [[directed graph]] with three [[Vertex (graph theory)|vertices]] (blue circles) and three [[Edge (graph theory)|edges]] (black arrows).]]<br>

图1：A [[directed graph]] with three [[Vertex (graph theory)|vertices]] (blue circles) and three [[Edge (graph theory)|edges]] (black arrows).<br>

图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>'''）/顶点）和三条黑色箭头的边（边（图论）的有向图。

一个有三个蓝色圆圈（点（'''<font color="#ff8000">图论Graph Theory</font>'''）/顶点）和三条黑色箭头的边（边（图论）的有向图。

   --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）注意图的格式  转行写[图1： 英文加翻译内容]

   --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）注意图的格式  转行写[图1： 英文加翻译内容]

A [[directed graph with three vertices (blue circles) and three 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 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 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 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>'''(也称为节点或点) ，以及一组无向图的无序顶点对或有向图的有序对组成。这些连线称为边(也称为链接或直线) ，对于有向图，也称为箭头。顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。

一个图的数据结构由一个有限的(也可能是可变的)'''<font color="#ff8000">顶点集Set Of Vertices</font>'''(也称为节点或点) ，以及一组无向图的无序顶点对或有向图的有序对组成。这些连线称为边(也称为链接或直线) ，对于有向图，也称为箭头。顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。

  Adjacency list

  Adjacency list

'''<font color="#ff8000">邻接表Adjacency list</font>'''

'''<font color="#ff8000">邻接表Adjacency List</font>'''

: 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 (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.

  Adjacency matrix

  Adjacency matrix

'''<font color="#ff8000">邻接矩阵Adjacency matrix</font>'''

'''<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.

  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>'''。关于边和顶点的数据必须存储在外部。只有一个边的开销时可以存储在每对顶点之间。

一个二维矩阵，其中行表示'''<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.&nbsp;531.</ref>

; [[Incidence matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p.&nbsp;531.</ref>

  Incidence matrix

  Incidence matrix

'''<font color="#ff8000">关联矩阵Incidence matrix</font>'''

'''<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.

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 ∞.

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>'''跟随边的代价进行编码。假定不存在的边的代价为∞。

下表给出了在图上执行各种操作的'''<font color="#ff8000">时间复杂度Time Complexity</font>'''，对于每个表示，用 | <big>V</big> | 顶点数和 | <big>E</big> | 边数。在矩阵表示中，'''<font color="#32CD32">条目值</font>'''the entries跟随边的代价进行编码。假定不存在的边的代价为∞。

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 |², or if one must be able to quickly look up if there is an edge connecting two vertices.

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 |², 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>|² ，或者说如果有一条边连接两个顶点，那么所选取的数据结构必须能满足快速查找到数据才行。

邻接表通常是首选的，因为它们能有效地表示'''<font color="#ff8000">稀疏图Sparse Graph</font>'''。如果图是'''<font color="#ff8000">稠密图Dense Graph</font>'''的，那么邻接矩阵是首选的，即边的数目 |<big>E</big>| 接近于顶点的平方数，|<big>V</big>|² ，或者说如果有一条边连接两个顶点，那么所选取的数据结构必须能满足快速查找到数据才行。

== Parallel Graph Representations ==

== Parallel Graph Representations ==

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.

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>，因此计算它们是不可行的。相反，使用以下启发式。

图的划分需要仔细地进行——在低通信和甚至大小划分之间有一个权衡。但是图的划分是一个'''<font color="#ff8000"><big>np</big> 难问题NP-Hard Problem</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> 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> 可能的伙伴。

'''<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>是代码吗？这块儿没明白怎么搞

--信白该句存疑，</math>是代码吗？这块儿没明白怎么搞

* [[Graph traversal]] for graph walking strategies

* [[Graph traversal]] for graph walking strategies

'''<font color="#ff8000">图的遍历Graph traversal</font>'''用于图遍历的策略

'''<font color="#ff8000">图的遍历Graph Traversal</font>'''用于图遍历的策略

* [[Graph database]] for graph (data structure) persistency

* [[Graph database]] for graph (data structure) persistency

'''<font color="#ff8000">图数据库 Graph database</font>'''用于图的（数据结构）持久性

'''<font color="#ff8000">图数据库 Graph Database</font>'''用于图的（数据结构）持久性

* [[Graph rewriting]] for rule based transformations of graphs (graph data structures)

* [[Graph rewriting]] for rule based transformations of graphs (graph data structures)

'''<font color="#ff8000">图重构 Graph rewriting</font>'''用于用于基于规则的图形转换（图数据结构）

'''<font color="#ff8000">图重构 Graph Rewriting</font>'''用于用于基于规则的图形转换（图数据结构）

* [[Graph drawing software]] for software, systems, and providers of systems for drawing graphs

* [[Graph drawing software]] for software, systems, and providers of systems for drawing graphs

'''<font color="#ff8000">画图软件 Graph drawing software</font>用于绘制图形的软件、系统和系统提供商

'''<font color="#ff8000">画图软件 Graph Drawing Software</font>用于绘制图形的软件、系统和系统提供商

   --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）see also记得翻译完全

   --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）see also记得翻译完全

   --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）可以看看之前发的链接“集智百科翻译团队新手指南”按着上面的要求再核对一下 比如专业名词标橙 疑难句标绿

   --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）可以看看之前发的链接“集智百科翻译团队新手指南”按着上面的要求再核对一下 比如专业名词标橙 疑难句标绿