用vector实现邻接表
时间: 2023-10-21 12:05:39 浏览: 81
邻接表是一种表示图的数据结构,其中每个节点都对应着一个链表,存储与其相邻的节点。使用vector实现邻接表的步骤如下:
1. 定义一个vector<vector<int>>类型的变量adj_list,其中adj_list[i]表示与节点i相邻的节点列表。
2. 对于每个节点i,将其相邻的节点存储在adj_list[i]中,可以使用push_back()函数将相邻节点逐个加入adj_list[i]中。
下面是一个简单的使用vector实现邻接表的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m; // n表示节点数,m表示边数
cin >> n >> m;
vector<vector<int>> adj_list(n); // 定义邻接表
for (int i = 0; i < m; ++i) {
int u, v; // u, v表示一条边的两个端点
cin >> u >> v;
adj_list[u].push_back(v); // 将v加入u的邻接表中
adj_list[v].push_back(u); // 将u加入v的邻接表中(无向图)
}
// 遍历邻接表输出
for (int i = 0; i < n; ++i) {
cout << "Node " << i << " is adjacent to: ";
for (int j = 0; j < adj_list[i].size(); ++j) {
cout << adj_list[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
这段代码读入了节点数n和边数m,然后使用vector<vector<int>>类型的变量adj_list表示邻接表。对于每条边,使用push_back()函数将相邻节点加入对应的邻接表中。最后遍历邻接表输出结果。
需要注意的是,这里使用的是无向图的邻接表实现方式,如果是有向图,需要分别将每条边的起点和终点加入对应节点的邻接表中。