所以图用c++储存按照以上步骤需要用到什么数据类型,内存空间,怎么样访问数据和释放内存数据呢
时间: 2024-02-20 15:01:45 浏览: 29
在 C++ 中,可以使用邻接表或邻接矩阵来存储图。
1. 邻接表存储图
邻接表是一种链式存储结构,用于表示图中顶点之间的关系,它的本质是一个数组,每个数组元素对应一个顶点,数组元素的值是与该顶点相邻的顶点的链表。邻接表适用于表示稀疏图,因为只有与该顶点相邻的顶点才会被存储,而其他顶点则不需要存储。
邻接表的实现可以使用 STL 中的 vector 或 list 容器,其中 vector 容器用于存储数组元素,list 容器用于存储链表。以下是一个使用 vector 和 list 实现的邻接表代码示例:
```c++
#include <iostream>
#include <vector>
#include <list>
using namespace std;
const int MAXN = 100; // 最大顶点数量
int n, m; // n 表示顶点数,m 表示边数
vector<list<int>> adj(MAXN + 1); // 邻接表
int main() {
cin >> n >> m;
// 读入边
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
// 无向图,需要添加两个方向的边
adj[u].push_back(v);
adj[v].push_back(u);
}
// 遍历邻接表,输出每个顶点的邻居
for (int i = 1; i <= n; i++) {
cout << "Vertex " << i << " neighbors: ";
for (auto v : adj[i]) {
cout << v << " ";
}
cout << endl;
}
return 0;
}
```
在上面的代码中,我们使用了 vector 容器来存储邻接表,使用 list 容器来存储链表。`vector<list<int>> adj(MAXN+1)` 定义了一个名为 adj 的邻接表,其中 adj[i] 对应的就是顶点 i 的链表。`adj[u].push_back(v)` 表示在顶点 u 的链表中添加一个值为 v 的元素。
2. 邻接矩阵存储图
邻接矩阵是一种二维数组,用于表示图中顶点之间的关系,它的本质是一个矩阵,其中矩阵元素的值表示两个顶点之间是否有边相连。邻接矩阵适用于表示稠密图,因为需要存储的信息很多,所以需要使用二维数组来存储。
邻接矩阵的实现可以使用 C++ 的二维数组来实现,以下是一个邻接矩阵的代码示例:
```c++
#include <iostream>
using namespace std;
const int MAXN = 100; // 最大顶点数量
int n, m; // n 表示顶点数,m 表示边数
int mat[MAXN + 1][MAXN + 1]; // 邻接矩阵
int main() {
cin >> n >> m;
// 初始化邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
mat[i][j] = 0; // 初始值为 0,表示没有边相连
}
}
// 读入边
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
// 无向图,需要添加两个方向的边
mat[u][v] = 1;
mat[v][u] = 1;
}
// 遍历邻接矩阵,输出每个顶点的邻居
for (int i = 1; i <= n; i++) {
cout << "Vertex " << i << " neighbors: ";
for (int j = 1; j <= n; j++) {
if (mat[i][j] == 1) {
cout << j << " ";
}
}
cout << endl;
}
return 0;
}
```
在上面的代码中,我们使用了一个二维数组来表示邻接矩阵,`int mat[MAXN+1][MAXN+1]` 定义了一个名为 mat 的邻接矩阵,其中 mat[i][j] 的值表示顶点 i 和顶点 j 之间是否有边相连。`mat[u][v]=1` 表示在顶点 u 和顶点 v 之间添加一条边。
访问邻接表和邻接矩阵中的数据非常简单,只需要按照数组或链表的访问方式即可,例如 `adj[i]` 表示访问邻接表中顶点 i 的链表,`mat[i][j]` 表示访问邻接矩阵中顶点 i 和顶点 j 之间的边。
释放邻接表和邻接矩阵的内存空间也非常简单,在 C++ 中,vector 和 list 容器会在作用域结束时自动销毁,而二维数组在使用完后不需要手动释放内存空间。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)