实现图的邻接矩阵存储结构,并实现图的创建和计算项点的度操作。
时间: 2024-02-01 19:15:15 浏览: 23
邻接矩阵是一种常见的图的存储方式,通过二维数组来表示图的各个顶点之间的关系。具体实现过程如下:
1. 定义一个二维数组AdjMatrix,用于存储图的邻接矩阵。其中,AdjMatrix[i][j]的值为1表示图中存在从顶点i到顶点j的边;值为0表示不存在从顶点i到顶点j的边。
2. 根据用户输入的顶点数和边数,动态申请二维数组的空间。
3. 根据用户输入的边的起点和终点,将对应的AdjMatrix[i][j]的值置为1。
4. 计算某一顶点的度,只需遍历该顶点所在行的所有元素,并统计值为1的元素个数即可。
下面是具体的实现代码:
```c++
#include <iostream>
using namespace std;
int main() {
int vnum, enum_;
cout<<"请输入图的顶点数和边数:";
cin>>vnum>>enum_;
int** AdjMatrix = new int*[vnum]; //动态申请二维数组空间
for(int i=0;i<vnum;i++){
AdjMatrix[i] = new int[vnum];
for(int j=0;j<vnum;j++){
AdjMatrix[i][j] = 0; //邻接矩阵初始化为0
}
}
cout<<"请按顺序输入每条边的起点和终点:"<<endl;
for(int i=0;i<enum_;i++){
int start, end;
cin>>start>>end;
AdjMatrix[start][end] = 1; //标记邻接矩阵中的边
}
cout<<"请输入要计算度的顶点编号:";
int vertex;
cin>>vertex;
int degree = 0;
for(int i=0;i<vnum;i++){
if(AdjMatrix[vertex][i] == 1){
degree++;
}
}
cout<<"该顶点的度为:"<<degree<<endl;
return 0;
}
```
需要注意的是,邻接矩阵存储方式会占用大量的空间,对于较大的图会造成空间浪费,因此在实际应用中需要根据具体情况选择合适的存储方式。