邻接矩阵表示法创建无向图 代码
时间: 2023-10-23 18:29:13 浏览: 148
下面是使用邻接矩阵表示法创建无向图的代码示例,其中使用了二维数组来存储邻接矩阵:
```c++
#include<iostream>
using namespace std;
const int MAXN = 100; // 图的最大节点数
int graph[MAXN][MAXN]; // 邻接矩阵表示法
int n, m; // n 表示节点数,m 表示边数
int main()
{
cin >> n >> m; // 输入节点数和边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入一条边的两个端点
graph[u][v] = 1; // 标记有一条从 u 到 v 的边
graph[v][u] = 1; // 由于是无向图,所以还要标记有一条从 v 到 u 的边
}
return 0;
}
```
以上代码实现了使用邻接矩阵表示法创建无向图的功能,可以在输入节点数和边数后,逐个输入边的两个端点,然后标记对应的邻接矩阵元素。
相关问题
7-1 邻接矩阵表示法创建无向图代码
以下是使用邻接矩阵表示法创建无向图的代码示例:
```c++
#include <iostream>
using namespace std;
const int MAXV = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大
int G[MAXV][MAXV]; // 邻接矩阵
int n, m; // 顶点数和边数
void createGraph() {
cin >> n >> m; // 输入顶点数和边数
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
G[i][j] = INF;
}
}
// 读入边的信息,建图
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w; // 读入一条边的起点、终点和权值
G[u][v] = w;
G[v][u] = w; // 无向图需要将两个方向都加上边权
}
}
int main() {
createGraph();
return 0;
}
```
在上面的代码中,我们使用二维数组 `G` 来表示邻接矩阵,其中 `G[i][j]` 表示顶点 `i` 到顶点 `j` 的边权值。由于是无向图,所以需要将两个方向都加上边权,即 `G[u][v] = w; G[v][u] = w;`。在读入边的信息后,我们需要遍历整个邻接矩阵,将未初始化的元素赋值为无穷大 `INF`,表示两个顶点之间没有边相连。
邻接矩阵表示法创建无向图
邻接矩阵是一种表示图的方式,用矩阵表示图中各个顶点之间的关系。对于无向图,邻接矩阵是一个对称矩阵,矩阵中的每个元素表示相邻顶点之间的边的数量或权重。
创建无向图的邻接矩阵表示法的步骤如下:
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 之间有一条边。
阅读全文