python 实现图的邻接矩阵存储,包括建立、输出,输出指定顶点的边信息
时间: 2024-02-06 15:09:06 浏览: 27
实现图的邻接矩阵存储,可以用一个二维数组来存储。具体实现步骤如下:
1. 定义一个二维数组,表示图的邻接矩阵。如果图有 n 个顶点,那么数组的大小为 n * n。
2. 初始化邻接矩阵,将所有元素都置为 0。
3. 对于每一条边 (u, v),将邻接矩阵中的第 u 行第 v 列和第 v 行第 u 列的元素置为 1,表示这两个顶点之间有一条边。
4. 如果还需要输出指定顶点的边信息,可以遍历邻接矩阵中该顶点所在的行或列,找到值为 1 的元素,表示该顶点与另外一个顶点之间有一条边。
下面是一个 Python 实现示例:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u, v):
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def get_edge_info(self, u):
for v in range(self.num_vertices):
if self.adj_matrix[u][v] == 1:
print(f"Vertex {u} is connected to vertex {v}")
```
这个类中,`num_vertices` 表示图的顶点数,`adj_matrix` 是一个二维数组,表示邻接矩阵。`add_edge` 方法用于添加边,`get_edge_info` 方法用于输出指定顶点的边信息。下面是一个使用示例:
```python
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
for i in range(g.num_vertices):
g.get_edge_info(i)
```
这个示例中,我们创建了一个有 4 个顶点的图,然后添加了三条边。最后遍历了每一个顶点,输出了与之相邻的顶点信息。输出结果如下:
```
Vertex 0 is connected to vertex 1
Vertex 0 is connected to vertex 2
Vertex 1 is connected to vertex 0
Vertex 1 is connected to vertex 3
Vertex 2 is connected to vertex 0
Vertex 3 is connected to vertex 1
```