is there other way to create adjacency list without creating 3 classes?
#Some question about graph
primal jay
proud steppeBOT
steep sapphire
is there other way to create adjacency list without creating 3 classes?
of course there is
vector<vector<int>> g
whereall vertexes are numbered fron 0 to n-1 where n is the total vertex count, g[i] are all the one-directional edges starting from vertex i
primal jay
of course there is
vector<vector<int>> g
whereall vertexes are numbered fron 0 ...
no, adjacency list, not a matrix
steep sapphire
no, adjacency list, not a matrix
so tell me how you define an adjacency list
steep sapphire
first time i learnt adjacency list was when i was using js
💀
primal jay
const graph = {
a : ['b', 'c'],
b : ['d', 'e'],
c : ['w', etc]}
upbeat gorge
just curious what would be the problem of using 3 classes?
primal jay
just curious what would be the problem of using 3 classes?
just thinking of alternative ways of doing it
steep sapphire
```
const graph = {
a : ['b', 'c'],
b : ['d', 'e'],
c : ['w', etc]}
```
as I said, the vertexes I use are numbers fron 0 to n-1, not strings
it's the same thing
but it works faster
upbeat gorge
just thinking of alternative ways of doing it
fair enough :)
steep sapphire
you sure?
in javascript you are accessing dynamic fields from an object, a.k.a. a hashmap
which takes some time
with vectors you are accessing elements at index i, always instantly
primal jay
its not about languages
its about implementation
i just wanna find efficient way of creating adjacency list
steep sapphire
its about implementation
the same design shown in your link is what I use
why are you not believing me
steep sapphire
i just wanna find efficient way of creating adjacency list
I showed you the efficent way
steep sapphire
you are wrong, the time complexity for these operations when vector<vector<int>> is used is the same as the column "Adjacency list"
from the screenshot here
let me demonstrate
so, the graph from the link
a.k.a.
this thing
in C++ can be hardcoded like this
vector<vector<int>> g =
{
{},//vertex 0 does not connect to any other vertexes
{2,3}, //vertex 1 connects one-directional edges to vertex 2 and 3
{1,5}, //vertex 2 connects one-directional edges to vertex 5 and 1
{1,4}, //vertex 3 connects one-directional edges to vertex 1 and 4
{5,3}, //vertex 4 connects one-directional edges to vertex 5 and 3
{2,4}, //vertex 5 connects one-dimensional edges to vertex 2 and 4
}
@primal jay
primal jay
what if you have vertex 10^8
steep sapphire
what if you have vertex 10^8
wut
primal jay
thats tone of memory
steep sapphire
vertex 1 - {2,3}, 100000000 - {4,50}
vertex numbers must be consecutive integers starting from 0
what is this?
primal jay
vertex numbers must be consecutive integers starting from 0
so it goes like:
0,1,2,3,4,5,6,7 ... 9999997,9999998, 9999999,100000000?
steep sapphire
so it goes like:
0,1,2,3,4,5,6,7 ... 9999997,9999998, 9999999,100000000?
yes
when you vertexes are defined with something more compilcated, like random ints, or strings
you must make a one to one mapping of your vertexes and numbers from 0 to n-1
and construct your adjacency list
@primal jay anything else?
steep sapphire
why do adjacency lists use _list_?
because most languages like java, C#, C++, python call it a list
but C++ calls it vector
it's a dynamically resizable array under the hood
primal jay
why do c++ implementation use lists?
steep sapphire
by knowing exactly when vectors and linked lists are fast and when they are slow, you can create your graph to suit your time complexity requirements
steep sapphire
why do c++ implementation use lists?
you can use whatever STL container you want man
you gotta know their internals to decide when to use what
99% of the time vector<vector<int>> is used
because the graph's vertexes are read from the standard input
and the graph never resizes again