526
个编辑
更改
跳到导航
跳到搜索
第75行：
第75行： − + − 表示 第82行：
第81行： − 图形表示的不同数据结构在实践中的使用:+ 第94行：
第93行： − 顶点作为记录或对象存储，每个顶点存储一个相邻顶点列表。这种数据结构允许在顶点上存储额外的数据。如果边也存储为对象，那么可以存储额外的数据，在这种情况下，每个顶点存储它的关联边，每个边存储它的关联顶点。+ 第106行：
第105行： − + 第126行：
第125行： − +
→Representations
* <code>set_edge_value</code>(''G'', ''x'', ''y'', ''v''): sets the value associated with the edge (''x'', ''y'') to ''v''.
* <code>set_edge_value</code>(''G'', ''x'', ''y'', ''v''): sets the value associated with the edge (''x'', ''y'') to ''v''.
==Representations==
==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:
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]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 528–529; {{harvtxt|Goodrich|Tamassia|2015}}, pp. 361-362.</ref>
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.
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]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 529–530; {{harvtxt|Goodrich|Tamassia|2015}}, p. 363.</ref>
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. 531.</ref>
; [[Incidence matrix]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p. 531.</ref>
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>'''the entries跟随边的代价进行编码。假定不存在的边的代价为∞。
下表给出了在图上执行各种操作的'''<font color="#ff8000">时间复杂度 Time Complexity</font>'''，对于每个表达式，用 | <big>V</big> | 顶点数和 | <big>E</big> | 边数。在矩阵表示中，'''<font color="#32CD32">条目值</font>'''the entries跟随边的代价进行编码。假定不存在的边的值为∞。