编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成以下功能:1)建立如图1所示的有向图G的邻接矩阵,并输出;2)建立如图1所示的有向图G的邻接表,并输出;3)销毁图G的邻接表。
时间: 2023-12-03 19:44:17 浏览: 191
图的邻接矩阵和邻接表实现
以下是Python代码实现:
```python
class Vertex:
def __init__(self, value):
self.value = value
self.edges = []
def add_edge(self, vertex, weight=0):
self.edges.append({"vertex": vertex, "weight": weight})
class Graph:
def __init__(self):
self.vertices = []
def add_vertex(self, value):
self.vertices.append(Vertex(value))
def get_vertex(self, value):
for vertex in self.vertices:
if vertex.value == value:
return vertex
def add_edge(self, value1, value2, weight=0):
vertex1 = self.get_vertex(value1)
vertex2 = self.get_vertex(value2)
vertex1.add_edge(vertex2, weight)
def print_adjacency_matrix(self):
matrix = []
for vertex in self.vertices:
row = [0] * len(self.vertices)
for edge in vertex.edges:
row[self.vertices.index(edge["vertex"])] = edge["weight"]
matrix.append(row)
for row in matrix:
print(row)
def print_adjacency_list(self):
for vertex in self.vertices:
row = [str(vertex.value) + ": "]
for edge in vertex.edges:
row.append("(" + str(edge["vertex"].value) + ", " + str(edge["weight"]) + ")")
print(" ".join(row))
def destroy(self):
self.vertices = []
# 测试
g = Graph()
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_vertex("D")
g.add_vertex("E")
g.add_edge("A", "B", 4)
g.add_edge("A", "C", 1)
g.add_edge("B", "E", 4)
g.add_edge("C", "D", 3)
g.add_edge("D", "E", 1)
print("邻接矩阵:")
g.print_adjacency_matrix()
print("邻接表:")
g.print_adjacency_list()
g.destroy()
```
输出结果为:
```
邻接矩阵:
[0, 4, 1, 0, 0]
[0, 0, 0, 0, 4]
[0, 0, 0, 3, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 0, 0]
邻接表:
A: (B, 4) (C, 1)
B: (E, 4)
C: (D, 3)
D: (E, 1)
E:
```
阅读全文