邻接矩阵表示法创建无向图
时间: 2023-10-18 20:15:48 浏览: 162
邻接矩阵是一种表示图的方式,用矩阵表示图中各个顶点之间的关系。对于无向图,邻接矩阵是一个对称矩阵,矩阵中的每个元素表示相邻顶点之间的边的数量或权重。
创建无向图的邻接矩阵表示法的步骤如下:
1. 创建一个 n × n 的矩阵,其中 n 是图中顶点的数量。
2. 在矩阵中标记顶点的编号,可以按照任意顺序给顶点编号。
3. 对于每条边 (i, j),将矩阵中第 i 行第 j 列和第 j 行第 i 列的元素都置为 1,表示这两个顶点之间有一条边。
4. 如果图中有权重,则将矩阵中的元素改为相应的权重值。
下面是一个示例,展示如何用邻接矩阵表示法创建一个无向图:
假设有一个无向图,包含 5 个顶点和 7 条边,如下所示:
```
1---2
|\ /|
| X |
|/ \|
3---4
```
首先,我们创建一个 5 × 5 的矩阵:
```
1 2 3 4 5
---------------
1| 0 0 0 0 0
2| 0 0 0 0 0
3| 0 0 0 0 0
4| 0 0 0 0 0
5| 0 0 0 0 0
```
然后,我们按照顺序给顶点编号,并将边的信息填入矩阵中:
```
1 2 3 4 5
---------------
1| 0 1 1 1 0
2| 1 0 1 1 0
3| 1 1 0 1 0
4| 1 1 1 0 0
5| 0 0 0 0 0
```
这个矩阵就是该无向图的邻接矩阵表示法。注意,由于是无向图,矩阵是对称的。例如,第 1 行第 2 列和第 2 行第 1 列的值都是 1,表示顶点 1 和顶点 2 之间有一条边。
阅读全文