自定义图的邻接矩阵和邻接表两种存储结构。以下两项任选其一: (1)创建图的邻接矩阵,设计算法自动生成邻接表,或: (2)创建图的邻接表,设计算法自动生成邻接矩阵。 要求能够打印图的邻接矩阵和邻接表,进行验证。
时间: 2024-05-01 12:22:22 浏览: 167
我可以为您提供创建图的邻接矩阵并自动生成邻接表的算法。
首先,我们需要定义一个Graph类来表示图,其中包含邻接矩阵和邻接表两种存储结构。以下是一个基本的Graph类实现:
```python
class Graph:
def __init__(self, num_vertices):
# 邻接矩阵
self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
# 邻接表
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, src, dest):
# 在邻接矩阵中添加边
self.adj_matrix[src][dest] = 1
self.adj_matrix[dest][src] = 1
# 在邻接表中添加边
self.adj_list[src].append(dest)
self.adj_list[dest].append(src)
def print_adj_matrix(self):
# 打印邻接矩阵
for row in self.adj_matrix:
print(row)
def print_adj_list(self):
# 打印邻接表
for i, adjacents in enumerate(self.adj_list):
print(f"{i}: {adjacents}")
```
在上面的代码中,我们定义了一个Graph类,它有一个构造函数,用于初始化邻接矩阵和邻接表。我们还定义了一个add_edge()方法,用于向图中添加边。在这个方法中,我们首先在邻接矩阵中添加边,然后在邻接表中添加边。最后,我们还定义了两个方法print_adj_matrix()和print_adj_list(),用于打印邻接矩阵和邻接表。
现在,我们可以在Graph类中添加一个新的方法,用于从邻接矩阵生成邻接表。以下是这个方法的实现:
```python
def generate_adj_list(self):
self.adj_list = [[] for _ in range(len(self.adj_matrix))]
for i in range(len(self.adj_matrix)):
for j in range(len(self.adj_matrix[i])):
if self.adj_matrix[i][j] == 1:
self.adj_list[i].append(j)
```
在上面的代码中,我们遍历邻接矩阵中的每一个元素。如果邻接矩阵中的值是1,说明有一条边,我们就在邻接表中添加这条边。最后,我们将生成的邻接表覆盖Graph类中原有的邻接表。
现在,我们可以创建一个Graph对象,向其中添加一些边,然后打印邻接矩阵和邻接表,最后生成邻接表并再次打印邻接表来验证我们的算法。
```python
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
print("Adjacency Matrix:")
g.print_adj_matrix()
print("Adjacency List:")
g.print_adj_list()
g.generate_adj_list()
print("Generated Adjacency List:")
g.print_adj_list()
```
运行上面的代码,我们可以看到以下输出:
```
Adjacency Matrix:
[0, 1, 0, 0, 1]
[1, 0, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 1, 0, 1, 0]
Adjacency List:
0: [1, 4]
1: [0, 2, 3, 4]
2: [1, 3]
3: [1, 2, 4]
4: [0, 1, 3]
Generated Adjacency List:
0: [1, 4]
1: [0, 2, 3, 4]
2: [1, 3]
3: [1, 2, 4]
4: [0, 1, 3]
```
我们可以看到邻接矩阵和邻接表都被正确地打印出来了,并且生成的邻接表也与原始的邻接表相同,因此我们的算法是正确的。
阅读全文
相关推荐
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![text/x-c](https://img-home.csdnimg.cn/images/20250102104920.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![-](https://img-home.csdnimg.cn/images/20241231044955.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)