将使用邻接矩阵存储的图转换成邻接表的存储的代码,用c++实现
时间: 2024-03-24 20:40:17 浏览: 66
将邻接矩阵转换为邻接表需要遍历邻接矩阵中的每个元素,将对应的边加入到邻接表中。以下是 C++ 实现代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
// 邻接矩阵存储的图
int G[MAXN][MAXN];
int n, m; // n 为顶点数,m 为边数
// 邻接表存储的图
vector<int> adjList[MAXN];
void convertToAdjList() {
// 遍历邻接矩阵中的每个元素
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (G[i][j] != 0) { // 如果有边
adjList[i].push_back(j); // 将边加入到邻接表中
}
}
}
}
int main() {
// 读入邻接矩阵存储的图
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
G[u][v] = 1;
G[v][u] = 1; // 无向图需要加上这一行
}
// 转换为邻接表存储的图
convertToAdjList();
// 输出邻接表存储的图
for (int i = 1; i <= n; i++) {
cout << i << ": ";
for (int j = 0; j < adjList[i].size(); j++) {
cout << adjList[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
该代码首先读入邻接矩阵存储的图,然后调用 `convertToAdjList` 函数将其转换为邻接表存储的图,并输出邻接表存储的图。注意,这里假设了输入的是无向图,因此需要将邻接矩阵中的对称位置也赋值为 1。如果输入的是有向图,则不需要这一行。
阅读全文