How is a graph possible with just an array?

#1

How can you implement a simple graph with
vector< int > graph [N+1];

#2

@Avi-Kasliwal-315786729062203
Graph is made up of nodes and edges so we have to just store them moreover the edge is nothing but a relation between two nodes so we create a vector with order equal to number of nodes, if edge exists between node (u, v) then we will push v inside vector’s index u, to indicate that u is connected with v. This concept is called adjacency list.
If you wish to read more about it please refer to this article

#3

what if there is an edge between u,v and u,w , how will a vector help then?

#4

we will push v inside vector[u] which would signify that u is connected to v hence the information that there is an edge between u, v is stored in vector

#5

for that graph should be vector< vector <int> >, right?

#6

vector vec[N+1] constructs N+1 vectors itself

1 Like