实现图的存储,输出存储结构示意图的代码
时间: 2024-02-18 19:05:31 浏览: 27
以下是使用邻接矩阵和邻接表两种方式实现图的存储,并输出存储结构示意图的 Python 代码示例:
```python
# 使用邻接矩阵实现图的存储,并输出存储结构示意图
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0] * vertices for _ in range(vertices)]
def add_edge(self, v1, v2, weight=1):
self.adj_matrix[v1][v2] = weight
self.adj_matrix[v2][v1] = weight # 对于无向图,邻接矩阵是对称的
def print_graph(self):
for row in self.adj_matrix:
print(row)
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.print_graph()
# 输出:
# [0, 1, 1, 0]
# [1, 0, 1, 1]
# [1, 1, 0, 1]
# [0, 1, 1, 0]
# 使用邻接表实现图的存储,并输出存储结构示意图
class Node:
def __init__(self, val):
self.val = val
self.next = None
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_list = [None] * vertices
def add_edge(self, v1, v2):
# 添加 v2 到 v1 的链表中
node = Node(v2)
node.next = self.adj_list[v1]
self.adj_list[v1] = node
# 添加 v1 到 v2 的链表中
node = Node(v1)
node.next = self.adj_list[v2]
self.adj_list[v2] = node
def print_graph(self):
for i in range(self.vertices):
print(i, end=": ")
node = self.adj_list[i]
while node:
print(node.val, end=" -> ")
node = node.next
print("None")
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.print_graph()
# 输出:
# 0: 2 -> 1 -> None
# 1: 3 -> 2 -> 0 -> None
# 2: 3 -> 1 -> 0 -> None
# 3: 2 -> 1 -> None
```
以上代码中,使用 `Graph` 类来表示图,`add_edge` 方法用于添加边,`print_graph` 方法用于输出存储结构示意图。其中使用 `adj_matrix` 数组来存储邻接矩阵,使用 `adj_list` 数组来存储邻接表,每个链表的头结点表示该顶点相邻的顶点。