如何用vector实现邻接表
时间: 2023-10-23 09:13:06 浏览: 89
邻接表是一种表示图的常用数据结构,可以用来存储图中每个节点的邻居节点。下面是使用vector实现邻接表的代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n = 5; // 图的节点数
vector<vector<int>> adj(n); // 定义邻接表
// 添加边
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(2);
adj[2].push_back(0);
adj[2].push_back(3);
adj[3].push_back(3);
// 输出邻接表
for(int i = 0; i < n; i++)
{
cout << i << " -> ";
for(int j = 0; j < adj[i].size(); j++)
cout << adj[i][j] << " ";
cout << endl;
}
return 0;
}
```
在这个例子中,我们首先定义了一个长度为n的vector,表示邻接表,每个vector中存储的是一个节点的邻居节点。然后我们添加了图中的边,最后输出邻接表,得到以下结果:
```
0 -> 1 2
1 -> 2
2 -> 0 3
3 -> 3
```
这个邻接表表示了一个有向图,节点0的邻居节点为1和2,节点1的邻居节点为2,节点2的邻居节点为0和3,节点3的邻居节点为3。