创建名为 ex060901_04.py 的文件,在文件中定义 3 个类,第一个是顶点的结点类, 第二个是弧的结点类,第三个是图类,该类包含存储图的邻接表及图的广度优先遍历方 法。请按以下步骤完成有向图的存储、广度优先遍历该图并输出对应的序列。 (1) 创建一个如图所示的有向图,并使用邻接表存储。 (2)以顶点 A 为起点,广度优先遍历该图。 (3)将广度优先遍历所得的序列输出
时间: 2024-02-03 18:12:08 浏览: 30
```python
class VertexNode:
def __init__(self, name):
self.name = name
self.first_arc = None
class ArcNode:
def __init__(self, adj_vex):
self.adj_vex = adj_vex
self.next_arc = None
class Graph:
def __init__(self):
self.vertex_list = []
def add_vertex(self, name):
vertex_node = VertexNode(name)
self.vertex_list.append(vertex_node)
def add_arc(self, start, end):
start_index = -1
end_index = -1
for i, v in enumerate(self.vertex_list):
if v.name == start:
start_index = i
if v.name == end:
end_index = i
if start_index != -1 and end_index != -1:
break
if start_index == -1 or end_index == -1:
return
arc_node = ArcNode(end_index)
if not self.vertex_list[start_index].first_arc:
self.vertex_list[start_index].first_arc = arc_node
else:
p = self.vertex_list[start_index].first_arc
while p.next_arc:
p = p.next_arc
p.next_arc = arc_node
def bfs_traverse(self, start):
visited = [False] * len(self.vertex_list)
queue = []
start_index = -1
for i, v in enumerate(self.vertex_list):
if v.name == start:
start_index = i
break
if start_index == -1:
return
visited[start_index] = True
queue.append(start_index)
while queue:
v_index = queue.pop(0)
print(self.vertex_list[v_index].name, end=" ")
arc_node = self.vertex_list[v_index].first_arc
while arc_node:
adj_v_index = arc_node.adj_vex
if not visited[adj_v_index]:
visited[adj_v_index] = True
queue.append(adj_v_index)
arc_node = arc_node.next_arc
if __name__ == "__main__":
g = Graph()
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_vertex("D")
g.add_vertex("E")
g.add_vertex("F")
g.add_arc("A", "B")
g.add_arc("A", "C")
g.add_arc("B", "D")
g.add_arc("B", "E")
g.add_arc("C", "E")
g.add_arc("D", "F")
g.add_arc("E", "F")
print("BFS Traversal:")
g.bfs_traverse("A")
```
输出结果:
```
BFS Traversal:
A B C D E F
```