怎样建立无向图的邻接矩阵存储图
时间: 2023-09-06 22:10:16 浏览: 48
建立无向图的邻接矩阵可以使用一个二维数组来存储。假设有 $n$ 个顶点,则该数组的大小为 $n\times n$。邻接矩阵中的每个元素 $a_{i,j}$ 表示顶点 $i$ 和顶点 $j$ 之间是否存在边,如果存在边,则 $a_{i,j}$ 的值为 $1$,否则为 $0$。
邻接矩阵的建立步骤如下:
1. 初始化一个 $n\times n$ 的二维数组 $adjMatrix$,将所有元素都初始化为 $0$。
2. 对于每条边 $(i,j)$,将 $adjMatrix[i][j]$ 和 $adjMatrix[j][i]$ 的值都设为 $1$,表示这两个顶点之间有一条边。
3. 最终得到的 $adjMatrix$ 就是无向图的邻接矩阵。
下面是一个示例代码实现,假设有 $n$ 个顶点和 $m$ 条边:
```python
n = 5 # 顶点数
m = 7 # 边数
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)] # 边列表
# 初始化邻接矩阵
adjMatrix = [[0] * n for _ in range(n)]
# 填充邻接矩阵
for i, j in edges:
adjMatrix[i][j] = adjMatrix[j][i] = 1
# 输出邻接矩阵
for row in adjMatrix:
print(row)
```
输出结果为:
```
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 0]
[1, 1, 0, 1, 1]
[0, 1, 1, 0, 1]
[0, 0, 1, 1, 0]
```
其中第 $i$ 行第 $j$ 列的元素表示顶点 $i$ 和顶点 $j$ 之间是否存在边。