根据图的抽象数据类型定义,使用邻接矩阵或邻接表实现一个图
时间: 2024-02-11 08:07:08 浏览: 49
好的,我会根据图的抽象数据类型定义,介绍邻接矩阵和邻接表两种方式来实现一个图。
1. 邻接矩阵
邻接矩阵是一个二维数组,其中的每个元素表示两个顶点之间是否存在边,如果存在则为1,否则为0。我们可以使用一个一维数组来存储顶点信息,顶点的编号可以作为数组下标。
下面是使用邻接矩阵实现图的示例代码:
```python
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.graph = [[0] * vertices for _ in range(vertices)]
def add_edge(self, u, v):
self.graph[u][v] = 1
self.graph[v][u] = 1
def print_graph(self):
for i in range(self.vertices):
for j in range(self.vertices):
print(self.graph[i][j], end=" ")
print()
```
2. 邻接表
邻接表是一个由链表构成的数组,其中的每个链表表示一个顶点的邻接点集合。我们可以使用一个字典来存储顶点信息,顶点的编号可以作为字典的键。
下面是使用邻接表实现图的示例代码:
```python
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, v):
self.graph[v] = []
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def print_graph(self):
for v in self.graph:
print(v, end=" ")
for u in self.graph[v]:
print("->", u, end=" ")
print()
```
以上就是使用邻接矩阵和邻接表两种方式实现图的示例代码。希望能对你有所帮助!
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)
![](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)