array of vectors or vector of arrays?

Question

I'm new to C++ STL, and I'm having trouble comprehending the graph representation.

vector<int> adj[N]; 

So does this create an array of type vector or does this create a vector of arrays? The BFS code seems to traverse through a list of values present at each instance of adj[i], and hence it seems works like an array of vectors. Syntax for creating a vector is:

vector<int> F; 

which would effectively create a single dimensional vector F.

What is the difference between

vector< vector<int> > N;  

and

vector<int> F[N] 

Answer 1

So does this (vector<int> adj[N];) create an array of type vector or does this create a vector of arrays?

It creates array of vectors

What is the difference between

vector< vector<int> > N;  

and

vector<int> F[N] 

In the first case you are creating a dynamic array of dynamic arrays (vector of vectors). The size of each vector could be changed at the run-time and all objects will be allocated on the heap.

In the second case you are creating a fixed-size array of vectors. You have to define N at compile-time, and all vectors will be placed on the stack^†, however, each vector will allocate elements on the heap.

I'd always prefer vector of vectors case (or the matrix, if you could use third-party libraries), or std::array of std::arrays in case of compile-time sizes.

I'm new to C++ STL, and I'm having trouble comprehending the graph representation.

You may also represent graph as a std::unordered_map<vertex_type,std::unordered_set<vertex_type>>, where vertex_type is the type of vertex (int in your case). This approach could be used in order to reduce memory usage when the number of edges isn't huge.

---

^†: To be precise - not always on stack - it may be a part of a complex object on the heap. Moreover, C++ standard does not define any requirements for stack or heap, it provides only requirements for storage duration, such as automatic, static, thread or dynamic.