编写一个python代码图的实验程序,设计邻接表类AdjGraph和邻接矩阵类MatGraph,由带权有向图的边数组a创建邻接表G,由G转换为邻接矩阵g,再由g转换为邻接表G1,输出G、g和G1,用相关数据进行测试。
时间: 2024-02-20 19:56:03 浏览: 88
python-graph-implementation:无向和有向图类的Python实现
好的,以下是一个示例程序:
```python
class Vertex:
def __init__(self, value):
self.value = value
self.adjacent = {}
def add_adjacent(self, vertex, weight=0):
self.adjacent[vertex] = weight
class AdjGraph:
def __init__(self, edges):
self.vertices = {}
for edge in edges:
start, end, weight = edge
if start not in self.vertices:
self.vertices[start] = Vertex(start)
if end not in self.vertices:
self.vertices[end] = Vertex(end)
self.vertices[start].add_adjacent(self.vertices[end], weight)
def __str__(self):
result = "Adjacency List:\n"
for vertex in self.vertices.values():
result += "{}: {}\n".format(vertex.value, [adjacent.value for adjacent in vertex.adjacent])
return result
class MatGraph:
def __init__(self, edges):
self.vertices = []
self.mat = []
vertex_dict = {}
for edge in edges:
start, end, weight = edge
if start not in vertex_dict:
vertex_dict[start] = len(self.vertices)
self.vertices.append(start)
if end not in vertex_dict:
vertex_dict[end] = len(self.vertices)
self.vertices.append(end)
if len(self.mat) <= vertex_dict[start]:
self.mat += [[0] * (len(self.vertices) - len(self.mat)) for _ in range(len(self.mat), vertex_dict[start] + 1)]
self.mat[vertex_dict[start]][vertex_dict[end]] = weight
def __str__(self):
result = "Adjacency Matrix:\n"
for row in self.mat:
result += str(row) + "\n"
return result
def mat_to_adj(mat):
edges = []
for i in range(len(mat)):
for j in range(len(mat[i])):
if mat[i][j] != 0:
edges.append((i, j, mat[i][j]))
return AdjGraph(edges)
edges = [(0, 1, 5), (0, 2, 3), (1, 3, 7), (2, 1, 2), (3, 2, 1)]
G = AdjGraph(edges)
print(G)
g = MatGraph(edges)
print(g)
G1 = mat_to_adj(g.mat)
print(G1)
```
这个程序定义了一个 `Vertex` 类表示图中的节点,包含一个值和一个邻接表。`AdjGraph` 类表示邻接表,可以从边数组创建。`MatGraph` 类表示邻接矩阵,也可以从边数组创建。`mat_to_adj` 函数将邻接矩阵转换为邻接表。程序最后创建了一个带权有向图,并输出了邻接表、邻接矩阵和由邻接矩阵转换得到的邻接表。
阅读全文