编写一个图的实验程序,设计邻接表类AdjGraph和邻接矩阵类MatGraph,由带权有向图的边数组a创建邻接表G,由G转换为邻接矩阵g,再由g转换为邻接表G1,输出G、g和G1,用相关数据进行测试。python
时间: 2024-02-29 16:52:33 浏览: 95
以下是一个使用 Python 3 编写的程序,可以创建一个带权有向图的边数组 a,然后使用邻接表类 AdjGraph 和邻接矩阵类 MatGraph 创建邻接表 G 和邻接矩阵 g,最后将 g 转换为邻接表 G1 并进行输出。请注意,这个程序需要使用 NumPy 库进行矩阵操作:
```python
import numpy as np
class Edge:
def __init__(self, v1, v2, weight):
self.v1 = v1
self.v2 = v2
self.weight = weight
class AdjGraph:
def __init__(self, edges):
self.edges = edges
self.nodes = set([e.v1 for e in edges] + [e.v2 for e in edges])
self.adj_list = {v: [] for v in self.nodes}
for e in edges:
self.adj_list[e.v1].append((e.v2, e.weight))
def __str__(self):
return str(self.adj_list)
class MatGraph:
def __init__(self, edges):
self.edges = edges
self.nodes = set([e.v1 for e in edges] + [e.v2 for e in edges])
self.num_nodes = len(self.nodes)
self.adj_matrix = np.zeros((self.num_nodes, self.num_nodes))
for e in edges:
self.adj_matrix[e.v1, e.v2] = e.weight
def __str__(self):
return str(self.adj_matrix)
def to_adj_graph(self):
adj_list = {v: [] for v in self.nodes}
for i in range(self.num_nodes):
for j in range(self.num_nodes):
if self.adj_matrix[i, j] != 0:
adj_list[i].append((j, self.adj_matrix[i, j]))
return AdjGraph([Edge(k, v[0], v[1]) for k, vs in adj_list.items() for v in vs])
# 创建带权有向图的边数组 a
a = [Edge(0, 1, 1), Edge(0, 3, 2), Edge(1, 2, 3), Edge(2, 0, 4), Edge(2, 3, 5)]
# 创建邻接表 G
G = AdjGraph(a)
print("邻接表 G:", G)
# 创建邻接矩阵 g
g = MatGraph(a)
print("邻接矩阵 g:", g)
# 将 g 转换为邻接表 G1
G1 = g.to_adj_graph()
print("邻接表 G1:", G1)
```
您可以调用这个程序并进行测试,以确保它可以正确地创建和转换有向图的邻接表和邻接矩阵。
阅读全文