编写算法,由依次输入的顶点数目、边的数目、各顶点的信息和各条边的信息建立无向图的邻接矩阵
时间: 2024-12-23 08:18:12 浏览: 1
创建无向图的邻接矩阵是一个常见的数据结构操作。以下是编写算法的一个基本步骤:
1. **初始化**:首先,你需要一个二维数组(矩阵),大小为顶点数乘以顶点数,因为每个顶点都会和其他所有顶点有邻接关系,所以初始矩阵全为0。
```python
def initialize_adj_matrix(vertices):
return [[0 for _ in range(vertices)] for _ in range(vertices)]
```
2. **输入信息**:然后,读取给定的顶点数、边数以及每条边的连接。你可以通过循环获取这些信息,例如:
- 使用`vertices`变量记录顶点数
- 对于每一条边,将起点和终点的索引设置为对应位置的值1,表示相连。
```python
def add_edge(adj_matrix, vertex1, vertex2):
adj_matrix[vertex1][vertex2] = 1
adj_matrix[vertex2][vertex1] = 1 # 因为无向图,双向连接
# 示例:
edges = [(0, 1), (1, 2), (2, 0)] # 假设这是给定的一些边
adj_matrix = initialize_adj_matrix(3)
for edge in edges:
add_edge(adj_matrix, *edge)
```
3. **输出结果**:最后,`adj_matrix`数组就代表了输入的无向图的邻接矩阵,其中非零元素表示两个顶点之间有边。
整个过程可以简化为函数形式,接受顶点数和边信息作为参数:
```python
def build_adj_matrix(vertices, edges):
adj_matrix = initialize_adj_matrix(vertices)
for edge in edges:
add_edge(adj_matrix, *edge)
return adj_matrix
```
阅读全文