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]
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.
Short Answer:
It's an array of vector <int>s.
Long Answer:
When reading a declaration such as
vector<int> adj[N];
The compiler uses a method known as the "spiral-" or "clockwise-rule" in order to interpret what it means. The idea behind the spiral rule is that you start at the variable name, and move outwards in a clockwise spiral in order to figure out what type of variable it is. For example:
char* str [10];
Can be interpreted like this:
____
| |
char* str [10];
|_________|
Making str an array of 10 char*s.
Therefore, vector<int> adj[N]; is an array of vectors rather than a vector of arrays
Practice makes perfect:
1: What does int * foo [ ]; mean?
Answer:
"foo" is an array of pointers to integers
2: What does int * (*foo [ ] )(); mean?
Answer:
"foo" is an array of pointers to functions returning pointers to integers
3: What does int * (*(*foo [ ] )())(); mean?
Answer:
"foo" is an array of pointers to functions returning pointers to functions returning pointers to integers
vector<int> arr[N];
It displays an array of vector, each array[i] would have a vector stored in it that can traverse through many values. It is like a an Array of Linked List where the heads are only stored in array[i] positions.
vector<vector<int> > N vs vector<int> F[N]
The difference between 2D Vector and an Array of Vector is that 2D Vectors can span in size while array of vectors have their dimension fixed for the array size.
Under the hood a vector still uses array, it is implementation specific but is safe to think that:
vector<int>
internally creates an int[].
What vectors gives you is that it abstract from you the part where if you want to re-size you don't have to re-allocate manually etc, it does that for you (plus much more of course).
When you do: vector<vector<int>> you are going to create a vector of vectors, meaning a 2D matrix. You can nest it as much as you want.
Vector takes in a type T and allocates an array of that type. so if you pass vector as type T, it will effectively do what you did in your first line, an array of vector<int>.
Hope it makes sense
