跳转至

7.3. 图的抽象数据类型

7.3. The Graph Abstract Data Type

图的抽象数据类型被定义为顶点和边的集合。顶点可以彼此连接，也可以是孤立的。边连接两个顶点，并且可能是加权的。

  • Graph() 创建一个新的空图。
  • add_vertex(vert) 向图中添加一个 Vertex 实例。
  • add_edge(from_vert, to_vert) 向图中添加一条新的有向边，连接两个顶点。
  • add_edge(from_vert, to_vert, weight) 向图中添加一条新的加权有向边，连接两个顶点。
  • get_vertex(vert_key) 查找图中名为 vert_key 的顶点。
  • get_vertices() 返回图中所有顶点的列表。
  • in 对于形式为 vertex in graph 的语句，如果给定顶点在图中，则返回 True，否则返回 False。

现在我们已经了解了图的抽象数据类型的定义，我们可以用几种方式在 Python 中实现它。我们将看到，使用不同的表示方法来实现上述抽象数据类型之间存在权衡。图的两种著名实现方式是 邻接矩阵 和 邻接表。我们将解释这两种选项，然后作为 Python 类实现其中一种。

The graph abstract data type is defined as a collection of vertices and edges. Vertices may be either connected to each other or isolated. Edges join two vertices and may be weighted.

  • Graph() creates a new empty graph.
  • add_vertex(vert) adds an instance of Vertex to the graph.
  • add_edge(from_vert, to_vert) adds a new directed edge to the graph that connects two vertices.
  • add_edge(from_vert, to_vert, weight) adds a new weighted directed edge to the graph that connects two vertices.
  • get_vertex(vert_key) finds the vertex in the graph named vert_key.
  • get_vertices() returns the list of all vertices in the graph.
  • in returns True for a statement of the form vertex in graph if the given vertex is in the graph, False otherwise.

Now that we have looked at the definition for the graph ADT, there are several ways we can implement it in Python. We will see that there are trade-offs in using different representations to implement the ADT described above. There are two well-known implementations of a graph, the adjacency matrix and the adjacency list. We will explain both of these options, and then implement one as a Python class.

最后更新: 2024年9月13日
创建日期: 2024年9月9日