c++ - 在 C++ 中使用 vector vector (二维 vector )的邻接表表示

Question

我们可以使用像 vector<int> adj[10]; 这样的一维 vector 在 BFS 中填充邻接表我们可以按如下方式填充该 vector :

main(){
    int x,y,nodes,edges;
    cin>>nodes>>edges;
    for(int i=0;i<edges;i++){
        cin>>x>>y;
        adj[x].push_back(y); //Insert y in adjacency list of x
    }
}

现在我们如何使用 2D vector (或 vector 的 vector )来填充邻接表而不是 1D vector 二维 vector 可以像vector<vector<int> >g;那么我们如何填充该 2D vector 以构建邻接列表？

Answer 1

比如说，x 的最大值可以是 n。
首先，您必须使用 n 个一维 vector 来初始化二维 vector 。
然后您可以像在示例中那样执行操作。

vector<vector<int> >g;
for(int i = 0; i<n; i++)
{
    vector<int>v;
    g.push_back(v);
}

g[0].push_back(3);
g[1].push_back(5);
cout<<g[0][0]<<endl;
cout<<g[1][0]<<endl;

或者您可以在声明时初始化 vector 。

vector<vector<int> >g(n);

g[0].push_back(3);
g[1].push_back(5);
cout<<g[0][0]<<endl;
cout<<g[1][0]<<endl;