7.6. 实现¶
7.6. Implementation
使用字典实现邻接表在 Python 中非常简单。在我们实现的图抽象数据类型中，我们将创建两个类：
Vertex 类，表示图中的每个顶点（见 Listing 1），以及 Graph 类，保存顶点的主列表（见 Listing 2）。
每个 Vertex 使用字典来跟踪与之连接的顶点和每条边的权重。这个字典叫做 neighbors。以下是 Vertex 类的代码。构造函数仅初始化 key（通常是一个字符串）和 neighbors 字典。set_neighbor 方法用于添加从该顶点到另一个顶点的连接。get_neighbors 方法返回邻接表中所有顶点，即 neighbors 实例变量所表示的内容。get_neighbor 方法返回从该顶点到传递参数的顶点的边的权重。
class Vertex:
def __init__(self, key):
self.key = key
self.neighbors = {}
def get_neighbor(self, other):
return self.neighbors.get(other, None)
def set_neighbor(self, other, weight=0):
self.neighbors[other] = weight
def __repr__(self):
return f"Vertex({self.key})"
def __str__(self):
return (
str(self.key)
+ " connected to: "
+ str([x.key for x in self.neighbors])
)
def get_neighbors(self):
return self.neighbors.keys()
def get_key(self):
return self.key
Graph 类（见下一个清单）包含一个字典，将顶点名称映射到顶点对象。在 Figure 4 中，这个字典对象由阴影灰色框表示。Graph 类还提供了添加顶点到图中和连接一个顶点到另一个顶点的方法。get_vertices 方法返回图中所有顶点的名称。此外，我们实现了 __iter__ 方法，使得可以轻松遍历特定图中的所有顶点对象。这两个方法使您可以按名称或对象本身遍历图中的顶点。
class Graph:
def __init__(self):
self.vertices = {}
def set_vertex(self, key):
self.vertices[key] = Vertex(key)
def get_vertex(self, key):
return self.vertices.get(key, None)
def __contains__(self, key):
return key in self.vertices
def add_edge(self, from_vert, to_vert, weight=0):
if from_vert not in self.vertices:
self.set_vertex(from_vert)
if to_vert not in self.vertices:
self.set_vertex(to_vert)
self.vertices[from_vert].set_neighbor(self.vertices[to_vert], weight)
def get_vertices(self):
return self.vertices.keys()
def __iter__(self):
return iter(self.vertices.values())
使用刚刚定义的 Graph 和 Vertex 类，以下 Python 会话创建了 Figure 2 中的图。首先，我们创建了六个编号从 0 到 5 的顶点。然后我们显示了顶点字典。注意到对于每个键 0 到 5，我们都创建了一个 Vertex 实例。接着，我们添加连接这些顶点的边。最后，一个嵌套循环验证图中每条边是否正确存储。您应该将该会话末尾的边列表输出与 Figure 2 进行对比。
>>> g = Graph()
>>> for i in range(6):
... g.set_vertex(i)
>>> g.vertices
{0: Vertex(0), 1: Vertex(1), 2: Vertex(2), 3: Vertex(3), 4: Vertex(4), 5: Vertex(5)}
>>> g.add_edge(0, 1, 5)
>>> g.add_edge(0, 5, 2)
>>> g.add_edge(1, 2, 4)
>>> g.add_edge(2, 3, 9)
>>> g.add_edge(3, 4, 7)
>>> g.add_edge(3, 5, 3)
>>> g.add_edge(4, 0, 1)
>>> g.add_edge(5, 4, 8)
>>> g.add_edge(5, 2, 1)
>>> for v in g:
... for w in v.get_neighbors():
... print(f"({v.get_key()}, {w.get_key()})")
...
(0, 1)
(0, 5)
(1, 2)
(2, 3)
(3, 4)
(3, 5)
(4, 0)
(5, 4)
(5, 2)
Using dictionaries, it is easy to implement the adjacency list in Python. In our implementation of the graph abstract data type we will create two classes:
Vertex, which will represent each vertex in the graph (see Listing 1) and Graph, which holds the master list of vertices (see Listing 2).
Each Vertex uses a dictionary to keep track of the vertices to which it is connected and the weight of each edge. This dictionary is called neighbors. The listing below shows the code for the Vertex class. The constructor simply initializes the key, which will typically be a string, and the neighbors dictionary. The set_neighbor method is used to add a connection from this vertex to another. The get_neighbors method returns all of the vertices in the adjacency list, as represented by the neighbors instance variable. The get_neighbor method returns the weight of the edge from this vertex to the vertex passed as a parameter.
class Vertex:
def __init__(self, key):
self.key = key
self.neighbors = {}
def get_neighbor(self, other):
return self.neighbors.get(other, None)
def set_neighbor(self, other, weight=0):
self.neighbors[other] = weight
def __repr__(self):
return f"Vertex({self.key})"
def __str__(self):
return (
str(self.key)
+ " connected to: "
+ str([x.key for x in self.neighbors])
)
def get_neighbors(self):
return self.neighbors.keys()
def get_key(self):
return self.key
The Graph class, shown in the next listing, contains a dictionary that maps vertex names to vertex objects. In Figure 4 this dictionary object is represented by the shaded gray box. Graph also provides methods for adding vertices to a graph and connecting one vertex to another. The get_vertices method returns the names of all of the vertices in the graph. In addition, we have implemented the __iter__ method to make it easy to iterate over all the vertex objects in a particular graph. Together, the two methods allow you to iterate over the vertices in a graph by name, or by the objects themselves.
class Graph:
def __init__(self):
self.vertices = {}
def set_vertex(self, key):
self.vertices[key] = Vertex(key)
def get_vertex(self, key):
return self.vertices.get(key, None)
def __contains__(self, key):
return key in self.vertices
def add_edge(self, from_vert, to_vert, weight=0):
if from_vert not in self.vertices:
self.set_vertex(from_vert)
if to_vert not in self.vertices:
self.set_vertex(to_vert)
self.vertices[from_vert].set_neighbor(self.vertices[to_vert], weight)
def get_vertices(self):
return self.vertices.keys()
def __iter__(self):
return iter(self.vertices.values())
Using the Graph and Vertex classes just defined, the following Python session creates the graph in Figure 2. First we create six vertices numbered 0 through 5. Then we display the vertex dictionary. Notice that for each key 0 through 5 we have created an instance of a Vertex. Next, we add the edges that connect the vertices together. Finally, a nested loop verifies that each edge in the graph is properly stored. You should check the output of the edge list at the end of this session against Figure 2.
>>> g = Graph()
>>> for i in range(6):
... g.set_vertex(i)
>>> g.vertices
{0: Vertex(0), 1: Vertex(1), 2: Vertex(2), 3: Vertex(3), 4: Vertex(4), 5: Vertex(5)}
>>> g.add_edge(0, 1, 5)
>>> g.add_edge(0, 5, 2)
>>> g.add_edge(1, 2, 4)
>>> g.add_edge(2, 3, 9)
>>> g.add_edge(3, 4, 7)
>>> g.add_edge(3, 5, 3)
>>> g.add_edge(4, 0, 1)
>>> g.add_edge(5, 4, 8)
>>> g.add_edge(5, 2, 1)
>>> for v in g:
... for w in v.get_neighbors():
... print("f({v.get_key()}, {w.get_key()})")
...
(0, 1)
(0, 5)
(1, 2)
(2, 3)
(3, 4)
(3, 5)
(4, 0)
(5, 4)
(5, 2)
创建日期: 2024年9月9日