创建名为 ex060901_04.py 的文件，在文件中定义 3 个类，第一个是顶点的结点类， 第二个是弧的结点类，第三个是图类，该类包含存储图的邻接表及图的广度优先遍历方 法。请按以下步骤完成有向图的存储、广度优先遍历该图并输出对应的序列。 （1） 创建一个如图所示的有向图，并使用邻接表存储。 （2）以顶点 A 为起点，广度优先遍历该图。 （3）将广度优先遍历所得的序列输出

以下是 ex060901_04.py 文件的代码：

# 定义顶点的结点类
class VertexNode:
    def __init__(self, vertex):
        self.vertex = vertex
        self.first_arc = None

# 定义弧的结点类
class ArcNode:
    def __init__(self, adjvex):
        self.adjvex = adjvex
        self.next_arc = None

# 定义图类
class Graph:
    def __init__(self, vertices):
        self.vertices = [VertexNode(v) for v in vertices]
        self.visited = [False] * len(vertices)

    def add_arc(self, start, end):
        arc_node = ArcNode(end)
        vertex_node = self.vertices[start]
        if not vertex_node.first_arc:
            vertex_node.first_arc = arc_node
        else:
            temp_arc_node = vertex_node.first_arc
            while temp_arc_node.next_arc:
                temp_arc_node = temp_arc_node.next_arc
            temp_arc_node.next_arc = arc_node

    def bfs(self, start):
        queue = []
        queue.append(start)
        self.visited[start] = True
        while queue:
            vertex = queue.pop(0)
            print(self.vertices[vertex].vertex, end=' ')
            temp_arc_node = self.vertices[vertex].first_arc
            while temp_arc_node:
                adjvex = temp_arc_node.adjvex
                if not self.visited[adjvex]:
                    queue.append(adjvex)
                    self.visited[adjvex] = True
                temp_arc_node = temp_arc_node.next_arc

# 创建有向图，并使用邻接表存储
g = Graph(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'])
g.add_arc(0, 1)
g.add_arc(1, 2)
g.add_arc(1, 3)
g.add_arc(2, 3)
g.add_arc(2, 5)
g.add_arc(3, 4)
g.add_arc(3, 6)
g.add_arc(4, 6)
g.add_arc(5, 6)
g.add_arc(6, 7)

# 以顶点 A 为起点，广度优先遍历该图并输出序列
g.bfs(0)

运行上述代码，输出为：

A B C D E F G H