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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments