c++如何实现图结构
时间: 2023-08-18 07:09:15 浏览: 39
在 C++ 中,可以使用邻接矩阵或邻接表来表示图结构。其中,邻接矩阵是一个二维数组,用于表示节点之间的连通性;邻接表是由链表或数组实现的一种数据结构,用于表示节点与其邻居节点之间的关系。
以下是使用邻接矩阵实现图的示例代码:
```c++
#include <iostream>
using namespace std;
const int MAXN = 100; // 最大节点数
int g[MAXN][MAXN]; // 邻接矩阵
int n; // 节点数
void addEdge(int u, int v) {
g[u][v] = 1;
g[v][u] = 1; // 无向图需要将两个方向都赋值为 1
}
int main() {
cin >> n; // 输入节点数
int m; // 边数
cin >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v);
}
// 输出邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << g[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
以下是使用邻接表实现图的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大节点数
vector<int> g[MAXN]; // 邻接表
int n; // 节点数
void addEdge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u); // 无向图需要将两个方向都添加
}
int main() {
cin >> n; // 输入节点数
int m; // 边数
cin >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v);
}
// 输出邻接表
for (int i = 0; i < n; i++) {
cout << i << ": ";
for (int j = 0; j < g[i].size(); j++) {
cout << g[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
以上是两种基本的图结构实现方法,具体使用哪种方法取决于具体应用场景和问题需求。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)