实现图的邻接矩阵存储结构,并实现图的创建和计算项点的度操作。
时间: 2024-02-01 09:16:19 浏览: 75
邻接矩阵是一种常见的图的存储结构,可以用一个二维数组来表示图中各个顶点之间的关系,其中数组中的每个元素表示两个顶点之间是否有边相连。
下面是一个简单的实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大点数
int n; // 点的个数
int m; // 边的个数
vector<int> G[MAXN]; // 邻接表
int mat[MAXN][MAXN]; // 邻接矩阵
// 创建图
void create_graph() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
mat[u][v] = mat[v][u] = 1;
}
}
// 计算点的度
int degree(int u) {
int deg = 0;
for (int v : G[u]) {
deg++;
}
return deg;
}
int main() {
create_graph();
// 输出邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << mat[i][j] << ' ';
}
cout << endl;
}
// 计算每个点的度
for (int i = 1; i <= n; i++) {
cout << "degree(" << i << ") = " << degree(i) << endl;
}
return 0;
}
```
输入格式为:
```
n m
u1 v1
u2 v2
...
um vm
```
其中 n 表示点的个数,m 表示边的个数,接下来 m 行表示每条边连接的两个点。
输出格式为:
```
邻接矩阵
每个点的度
```
其中邻接矩阵为一个 n×n 的矩阵,每个元素表示两个顶点之间是否有边相连,1 表示有边相连,0 表示没有边相连。每个点的度表示该点与其他点相连的边的数量。
阅读全文