274
个编辑
更改
跳到导航
跳到搜索
第25行：
第25行： − + 第89行：
第89行： − 邻接表+ 第101行：
第101行： − 邻接矩阵+ 第107行：
第107行： − 一个二维矩阵，其中行表示源顶点，列表示目标顶点。关于边和顶点的数据必须存储在外部。只有一个边的开销时可以存储在每对顶点之间。+ 第113行：
第113行： − 关联矩阵+ 第119行：
第119行： − + 第127行：
第127行： − 下表给出了在图上执行各种操作的时间复杂度，对于每个表示，用 | <big>V</big> | 顶点数和 | <big>E</big> | 边数。在矩阵表示中，条目值跟随边的代价进行编码。假定不存在的边的代价为∞。+ 第414行：
第414行： − 分布式存储<br>+ 第428行：
第428行： − +
无编辑摘要
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>'''(也称为节点或点) ，以及一组无向图的无序顶点对或有向图的有序对组成。这些连线称为边(也称为链接或直线) ，对于有向图，也称为箭头。顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。
Adjacency list
Adjacency list
'''<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>'''
: 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>'''。关于边和顶点的数据必须存储在外部。只有一个边的开销时可以存储在每对顶点之间。
; [[Incidence matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p. 531.</ref>
; [[Incidence matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p. 531.</ref>
Incidence matrix
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.
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> | 边数。在矩阵表示中，条目值跟随边的代价进行编码。假定不存在的边的代价为∞。
<sub>下标文字</sub>=== Distributed Memory ===
<sub>下标文字</sub>=== Distributed Memory ===
'''<font color="#ff8000">分布式存储Distributed Menory</font>'''<br>
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 [[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" />
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.
图的划分需要仔细地进行——在低通信和甚至大小划分之间有一个权衡。但是图的划分是一个<big>NP</big> 难问题，因此计算它们是不可行的。相反，使用以下启发式。
图的划分需要仔细地进行——在低通信和甚至大小划分之间有一个权衡。但是图的划分是一个'''<font color="#ff8000"><big>NP</big> 难问题NP-hard problem</font>，因此计算它们是不可行的。相反，使用以下启发式。