274
个编辑
更改
跳到导航
跳到搜索
第46行：
第46行： − + − + − + 第77行：
第77行： − + − 图形表示的不同数据结构在实践中使用:+ 第106行：
第106行： − 一个二维矩阵，其中行表示源顶点，列表示目标顶点。关于边和顶点的数据必须存储在外部。只有一个边的开销可以存储在每对顶点之间。+ 第118行：
第118行： − 一个二维布尔矩阵，其中行表示顶点，列表示边。条目指示行上的顶点是否与列上的边相关联。+ 第126行：
第126行： − +
无编辑摘要
图形''G'' 的数据结构提供的基本操作通常包括:
图形''G'' 的数据结构提供的基本操作通常包括:
--[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）变量斜体
--[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）变量斜体
* <code>adjacent</code>(''G''，''x'',''y''): tests whether there is an edge from the vertex ''x'' to the vertex ''y'';
* <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>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>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>remove_vertex</code>(''G'', ''x''): removes the vertex ''x'', if it is there;
==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>
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]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p. 531.</ref>
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 ∞.
下表给出了在图上执行各种操作的时间复杂度，对于每个表示，用 | v | 顶点数和 | e | 边数。在矩阵表示中，条目对跟随边的代价进行编码。假定不存在的边的代价为∞。
下表给出了在图上执行各种操作的时间复杂度，对于每个表示，用 | <big>V</big> | 顶点数和 | <big>E</big> | 边数。在矩阵表示中，条目值跟随边的代价进行编码。假定不存在的边的代价为∞。