Python实现有向图：邻接表及示例

本文介绍如何使用Python实现一个有向图，并通过邻接表来表示图的结构。

1. 代码实现pythonclass DirectedGraph: def init(self): self.graph = {}

def add_vertex(self, vertex):        if vertex not in self.graph:            self.graph[vertex] = []

def add_edge(self, start_vertex, end_vertex):        if start_vertex in self.graph and end_vertex in self.graph:            self.graph[start_vertex].append(end_vertex)

def print_graph(self):        for vertex in self.graph:            edges = ' '.join(self.graph[vertex])            print(f'{vertex}: {edges}')

创建图对象graph = DirectedGraph()

添加顶点graph.add_vertex('s')graph.add_vertex('v')graph.add_vertex('w')graph.add_vertex('q')graph.add_vertex('t')graph.add_vertex('y')graph.add_vertex('x')graph.add_vertex('z')graph.add_vertex('r')graph.add_vertex('u')

添加边graph.add_edge('s', 'v')graph.add_edge('w', 's')graph.add_edge('q', 's')graph.add_edge('q', 'w')graph.add_edge('q', 't')graph.add_edge('t', 'x')graph.add_edge('y', 'q')graph.add_edge('x', 'z')graph.add_edge('r', 'y')graph.add_edge('r', 'u')graph.add_edge('u', 'y')

打印图graph.print_graph()

输出结果：

s: vv: w: sq: s w tt: xy: qx: zz: r: y uu: y

2. 代码解读

• DirectedGraph类: 表示一个有向图。 * __init__方法：初始化图，使用一个字典self.graph存储图的信息，键为顶点，值为该顶点指向的顶点列表。 * add_vertex方法：向图中添加一个顶点。 * add_edge方法：向图中添加一条边，从start_vertex指向end_vertex。 * print_graph方法：打印图的邻接表表示。

• 示例: 代码中创建了一个DirectedGraph对象，并添加了指定的顶点和边，最终打印出该图的邻接表表示。

3. 图示

下图展示了代码所创建的有向图：

[图片：示例图的图形化表示]

注意: 图中箭头方向表示边的方向，例如，'s' 指向 'v'，表示存在一条从 's' 到 'v' 的有向边。