Understood each and every word♥️. Kudos to your hard work and dedication, you are the motivation behind a lot of people. Your hardwork inspires a lot of people to work hard. Thankyou for providing such a beautiful graph series keep posting such content ♥️, we all need this.
@take U forward the complexity at 6:44 if it is 0 indexed should be n*n or n*m ? and the complexity at 7:17 should be O(m) I guess . Please let me know
In the adj matrix code at 06:37 there will be adj[n+1][n+1], not adj[n+1][m+1]. We all understood this from your explanation. Thank you for such great playlists.💛
2D Vector (vector) Dynamic: Both dimensions (rows and columns) can be resized dynamically. Usage: Suitable when the number of vertices is not known at compile time or can change. Syntax: vector adjList(vertices); Array of Vectors (vector adj[]) Fixed Outer Dimension: The number of rows (vertices) is fixed at compile time. Dynamic Inner Dimension: The number of columns (edges per vertex) can change dynamically. Usage: Suitable when the number of vertices is known and fixed at compile time. Syntax: vector adj[n+1];
@@Surya77_6 because we have a vector corresponding to single integer, example 1 is connected to 2 and 3 so, key is 1 and have value in the form of vector containing 2 and 3
@@ProSol-im6znbro, if there no of edges depends upon the no of nodes, so we need adj[n+1][n+1], total of n*2 edges possible, what he typed was a mistake in the video
Its not a 1-D vector. Its aa array of vector. see it this way. How a 1-D vector is declared : vector adj(n+1); How an array of vectors is declared : vector adj[n+1]; Do you observe the difference between ( ) and [ ] ? Now you do :D
Some compilers like Visual C++ don't support variable length arrays. So you will get compilation error for using non-constant n and m as array indexes. In that case you can use vector as follows: //Adjacency Matrix representation =========================== #include #include using namespace std; int main() { int nodes, edges, u, v; cin >> nodes >> edges; // declare the Adjacency matrix vector adj; adj.resize(nodes + 1); // take edges as input for (int i = 0; i < edges; i++) { cin >> u >> v; adj[u][v] = 1; adj[v][u] = 1; } return 0; } //Adjacency List representation ========================= #include #include using namespace std; int main() { int nodes, edges, u, v; cin >> nodes >> edges; // declare the Adjacency list vector adj; adj.resize(nodes + 1); // take edges as input for (int i = 0; i < edges; ++i) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } return 0; }
@@harshitrautela6585 Honestly, DP. Because I feel its problems are more interesting than graphs and I generally like recursion more. Also, when Striver teaches it you really feel ADDICTED. It's soooo much more immersive than graphs. But it's up to you. The disadvantage of going with DP is you have to complete the recursion series first as a prerequisite, and it's longer than the graph series.
@@tasneemayham974I learned recursion from love Babbar but I still suck at it , is Striver's recursion playlist good? Also should I make notes or just learn the topic and apply it? I am asking this because I am confused and don't know how to move forward
@@Josuke217 I don't know Babbar. But I know that once I learned recursion from Striver, I didn't need to open any other CZcams video. It IS this good. And YESS definitely make notes. I learn and memorize better when I take notes. Learning goes both ways: note-taking and skill application. I know how you feel. Currently, I am stuck too. My Graph series Notes were destroyed because of water contact. I am soooo downnn!! 😥😥😥
//Thanku so much striver bhaiya for this amazing content ❤ //I have made a complete gist of this video in the code written below in C++ #include using namespace std; int main() { // Graph is a finite set of vertices and edges // total degree of undirected graph=2*Total edges // for directed graph degree is represented in terms of indegree and outdegree //degree of a vertex is defined as the no of edges attached with it int n, m; cout > n; cout > m; vector adj(n + 1, vector(m + 1, 0)); vector adj_list[n + 1]; for (int i = 1; i > v1 >> v2>>wt; adj[v1][v2] = wt; adj[v2][v1] = wt;//remove this line for directed graph adj_list[v1].push_back({v2,wt}); adj_list[v2].push_back({v1,wt});//remove this line for directed graph } //---------ADJACENCY MATRIX-------------------// // space complexity for undirected graph= O(V*V) // space complexity for directed graph : O(V*V) cout
The adjacency matrix is better if we are concerned about time complexity as it finds edge b/w nodes in O(1). Yes, in the case of something like a sparse graph, we should prefer an adjacency list otherwise we would waste too much space.
@@dravitgupta7927 maybe I was unclear in what I meant. I meant that (n+1)(n+1) should be the size, because the number of edges(m) don't matter, but the number of vertices(n) matters. Try reading my old comment once again.
when we declare an array of integers of size n, we say int arr[n] so we say the datatype is int. Here, we want to create an array of vectors (of type int) hence, vector arr[n+1] of size n+1.
I don't get this part where he says he says he using list to store the graph values. But he only define the structure like vector and later vector but how will he store multiple values on one index as he defined it. In both the approaches he is using a 2d array
@@mohakhiphop well vector of vector will take more space if we already declare the size. But the space will be same as vector adj[] if we store in a way so that it doesn't take extra space.
Okay, I was watching your previous playlist yesterday , and in that you said space complexity of Adjacency list is O(V+2E) which i didn't understood. Now, I came across this video in which it is O(2E) and I understood it. I know they are almost same but I want to know why did we add V in the space complexity in the old video .
Yes, I went through all the comments of those videos, and making sure I cover things which people were having doubts 😅 The addition of V was for the list creation. The list itself takes N space.
Hi Loved it... Great Explanation from scratch. And also as i read your community post. I think the audio quality has changed. In L1 the audio quality was kind of good, but in this there is a lot of disturbance. Also i liked the red colored Writing (specially when it fades after explaning) Loved the details.♥️♥️♥️
vector adj[n+1]- This is not 1D Vector. This is array of Vectors. Here (n+1) are vectors. In an array of vectors, each element (or index) of the array is itself a vector. vector adj(n+1); - This is 1D vector. Here we only 1 vector having (n+1) elements. This is due to the difference between ( ) and [ ].
Yes means you can store similar data in both just difference is First one is Array where each element is vector , Second is Vector of size n where each element is vector
@@takeUforward is it because of double the size property? What if we define size of 2d-vector beforehand? Something like below: vector adjList(n+1, vector(m+1)) Only asking this because array of vectors was not so intuitive to me atleast :')
00:03 Learn how to represent a graph in C++ or Java 02:05 Learn how to store edges in a graph using an adjacency matrix or a list. 04:07 Creating an adjacency matrix to represent edges between nodes 06:09 Storing a graph using adjacency list takes less space than n square method 08:15 Adjacency list stores neighbors of a node 10:12 Using adjacency list for graph storage 12:22 Learned how to store graphs using adjacency list and matrix 14:13 Store weights in pairs instead of single integers Crafted by Merlin AI.
After filling the adjacent list with edges and weight the size of adjacent list is showing 0, why ? ( Code is given below and size is printed in line no. 8 ) thanks :) // CODE FOR WEIGHTED GRAPH 1. int n,m; 2. cout > n; 4. cout > m; 6. vector adj[n+1]; 7. for(int i=0; i u >> v; cout > w; adj[u].push_back({v, w}); adj[v].push_back({u,w}); } 8. cout
You forgot to consider the space taken by the outer List while calculating total space in case of adjacency list Total space complexity = V + 2E => O(V + E), V space for an array of V vertices, each of which holds a vector, 2E (for undirected graphs), as each edge accounts for 2 list elements.
Lets continue the habit of commenting “understood” if you got the entire video.
Do follow me at Instagram: striver_79
Understood each and every word♥️. Kudos to your hard work and dedication, you are the motivation behind a lot of people. Your hardwork inspires a lot of people to work hard.
Thankyou for providing such a beautiful graph series keep posting such content ♥️, we all need this.
@take U forward the complexity at 6:44 if it is 0 indexed should be n*n or n*m ? and the complexity at 7:17 should be O(m) I guess . Please let me know
@@nisha_k22 You are right
understood
In the adj matrix code at 06:37 there will be adj[n+1][n+1], not adj[n+1][m+1]. We all understood this from your explanation. Thank you for such great playlists.💛
HA WOHI
MAI SOCH RHA THA
2D Vector (vector)
Dynamic: Both dimensions (rows and columns) can be resized dynamically.
Usage: Suitable when the number of vertices is not known at compile time or can change.
Syntax: vector adjList(vertices);
Array of Vectors (vector adj[])
Fixed Outer Dimension: The number of rows (vertices) is fixed at compile time.
Dynamic Inner Dimension: The number of columns (edges per vertex) can change dynamically.
Usage: Suitable when the number of vertices is known and fixed at compile time.
Syntax: vector adj[n+1];
It would be better if we use *map m* rather than *vector v[n+1]*
Why bro
@@Surya77_6 because we have a vector corresponding to single integer, example 1 is connected to 2 and 3 so, key is 1 and have value in the form of vector containing 2 and 3
For storing in adjacency matrix, it will be int adj[n][n] if nodes are numbered from 0 to n-1 and adj[n+1][n+1] if nodes are numbered from 1 to n
yes... even I was thinking the same during the lecture
why n+1
@@johnxina7496 Because of 1-based indexing, if you'll take it n then n-th node will not get added.
he also did a mistake of taking n+1 * m+1 it should be n+1 * n+1
I feel the matrix should be like adj[n+1][n+1] not adj[n+1][m+1]
yes this right
Can u say
How do u know those matrix
I don't have a proper idea about adj[n+1]
Ya I wasss about to comment this
@@ProSol-im6znbro, if there no of edges depends upon the no of nodes, so we need adj[n+1][n+1], total of n*2 edges possible, what he typed was a mistake in the video
adjacency list is vectoradj. right? and not just 1d vector
Yeah same doubt
han bhai same doubt mera bhi .
Its not a 1-D vector. Its aa array of vector.
see it this way.
How a 1-D vector is declared : vector adj(n+1);
How an array of vectors is declared : vector adj[n+1];
Do you observe the difference between ( ) and [ ] ? Now you do :D
@@ritabhsharma6627🙌
@@ritabhsharma6627 Thank you so much. I could never understand how he was able to store a list in a vector. Thanks for clearing my doubt.
Some compilers like Visual C++ don't support variable length arrays. So you will get compilation error for using non-constant n and m as array indexes. In that case you can use vector as follows:
//Adjacency Matrix representation
===========================
#include
#include
using namespace std;
int main() {
int nodes, edges, u, v;
cin >> nodes >> edges;
// declare the Adjacency matrix
vector adj;
adj.resize(nodes + 1);
// take edges as input
for (int i = 0; i < edges; i++) {
cin >> u >> v;
adj[u][v] = 1;
adj[v][u] = 1;
}
return 0;
}
//Adjacency List representation
=========================
#include
#include
using namespace std;
int main() {
int nodes, edges, u, v;
cin >> nodes >> edges;
// declare the Adjacency list
vector adj;
adj.resize(nodes + 1);
// take edges as input
for (int i = 0; i < edges; ++i)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
return 0;
}
At last, I was racking my head trying to understand how using vector we were able to represent a 2D matrix. Thanks, bro
@@srianshumahadas7178 Welcome!
int matrix[M][N] can be represented as vector matrix(M, vector(N)) .
I finished the ENTIRE dp series. THE BESSTTT. Now I am here for graphss!!
Thank youu sooo much Striver!!!
do you suggest completing graph or dp series before?
@@harshitrautela6585 Honestly, DP. Because I feel its problems are more interesting than graphs and I generally like recursion more. Also, when Striver teaches it you really feel ADDICTED. It's soooo much more immersive than graphs.
But it's up to you. The disadvantage of going with DP is you have to complete the recursion series first as a prerequisite, and it's longer than the graph series.
@@tasneemayham974I learned recursion from love Babbar but I still suck at it , is Striver's recursion playlist good? Also should I make notes or just learn the topic and apply it? I am asking this because I am confused and don't know how to move forward
@@Josuke217 I don't know Babbar. But I know that once I learned recursion from Striver, I didn't need to open any other CZcams video. It IS this good. And YESS definitely make notes. I learn and memorize better when I take notes. Learning goes both ways: note-taking and skill application.
I know how you feel. Currently, I am stuck too. My Graph series Notes were destroyed because of water contact. I am soooo downnn!! 😥😥😥
@@tasneemayham974 thanks , is the recursion series complete? Because someone told me striver has skipped some topics.
I just wanted to say that u are pure gem for us and keep going the way you are going. Lots of thanks 🙏🙏
//Thanku so much striver bhaiya for this amazing content ❤
//I have made a complete gist of this video in the code written below in C++
#include
using namespace std;
int main()
{
// Graph is a finite set of vertices and edges
// total degree of undirected graph=2*Total edges
// for directed graph degree is represented in terms of indegree and outdegree
//degree of a vertex is defined as the no of edges attached with it
int n, m;
cout > n;
cout > m;
vector adj(n + 1, vector(m + 1, 0));
vector adj_list[n + 1];
for (int i = 1; i > v1 >> v2>>wt;
adj[v1][v2] = wt;
adj[v2][v1] = wt;//remove this line for directed graph
adj_list[v1].push_back({v2,wt});
adj_list[v2].push_back({v1,wt});//remove this line for directed graph
}
//---------ADJACENCY MATRIX-------------------//
// space complexity for undirected graph= O(V*V)
// space complexity for directed graph : O(V*V)
cout
from past 3-4 months I was running away from the graph but I got some hope after watching this video. 😍
the best explanation of graphs till now... thanks striver
The adjacency matrix is better if we are concerned about time complexity as it finds edge b/w nodes in O(1). Yes, in the case of something like a sparse graph, we should prefer an adjacency list otherwise we would waste too much space.
@7:16 Time complexity to store the adjacency matrix would be O(m) and not O(n)
6:42 why is the matrix is [n+1][m+1] but previously u told [n+1][n+1]?
because in total, there are only n vertices. we dont care about the number of edges here as we can store any edge in the matrix format.
I think it's a typing mistake.
@@dravitgupta7927 maybe I was unclear in what I meant. I meant that (n+1)(n+1) should be the size, because the number of edges(m) don't matter, but the number of vertices(n) matters. Try reading my old comment once again.
@@ArnabJhaYT Got it👌.
@@ArnabJhaYT yes number of edges won't matter here
vector adj[n+1];
means => vector adj(n+1);
Correct me if I am wrong?
something i got stuck on myself, didn't notice the square brackets
it's a vector of array. Try to read it from right to left. At each index there is an empty vector.
when we declare an array of integers of size n, we say int arr[n] so we say the datatype is int. Here, we want to create an array of vectors (of type int) hence, vector arr[n+1] of size n+1.
@@tanishgupta7879 you mean array of vectors
I don't get this part where he says he says he using list to store the graph values. But he only define the structure like vector and later vector but how will he store multiple values on one index as he defined it. In both the approaches he is using a 2d array
bro he is using array of vectors `vector adj[n+1]`
Understood Bhaiya
We can also use this for representing adjacency list:
unordered_map list
Bhiya at 7:10 adjacency matrix should be of (n+1)*(n+1) size and not (n+1)*(m+1).
vector adj[n+1] basically means a vector of arrays right? so can we also declare it as vector of vectors?
Yes, which is adjacency matrix but it takes more space
@@rahulshah2685 no its right , vector[] is array of vector i.e. 2 d array
@@mohakhiphop well vector of vector will take more space if we already declare the size. But the space will be same as vector adj[] if we store in a way so that it doesn't take extra space.
@@DevanshuAugusty yep true💯
15:20 so for this it would be: vector adj[n+1] .... right?
no it should be vector adj(n+1);
"UNDERSTOOD BHAIYA!!"
Thank you, Striver 🙂
Okay, I was watching your previous playlist yesterday , and in that you said space complexity of Adjacency list is O(V+2E) which i didn't understood.
Now, I came across this video in which it is O(2E) and I understood it. I know they are almost same but I want to know why did we add V in the space complexity in the old video .
Yes, I went through all the comments of those videos, and making sure I cover things which people were having doubts 😅
The addition of V was for the list creation. The list itself takes N space.
Liked the video, notes taken, understood
Bhaiya itna deep kisi ne nhi samjhaya "Understood😉" Maja aa gaya
I am very lucky because I found you❤🎉🎉
amazing video sir ji
UnderStood Thanks for this amazing series
Hi Loved it... Great Explanation from scratch.
And also as i read your community post. I think the audio quality has changed. In L1 the audio quality was kind of good, but in this there is a lot of disturbance. Also i liked the red colored Writing (specially when it fades after explaning) Loved the details.♥️♥️♥️
his explanition is the worst ever, kunals, shardha didis explination is far better than his
For adjacency list, shouldn't it be vector< vector > adj(n+1) ; ???
vector adj[n+1]- This is not 1D Vector. This is array of Vectors. Here (n+1) are vectors. In an array of vectors, each element (or index) of the array is itself a vector.
vector adj(n+1); - This is 1D vector. Here we only 1 vector having (n+1) elements.
This is due to the difference between ( ) and [ ].
@@shivanibaliyan7276 I did not notice the third bracket at first. Yes it is a Vector of Arrays
US , Excited for learning graph
Thankyou Striver, Understood!
Best graph explanation🙌🏻🙌🏻
Great content and explanation
Shouldnt the size of adj in 6.57 be [n+1][n+1] instead of [n+1][m+1] ?
yes
very nice explanation
Understood! Great explanation as always, thank you very much!!
Thank you so much
Awesome Video..understood everything
Understood!
Understood
vector v[n] and vector v(n) are they same ???
Yes means you can store similar data in both just difference is
First one is Array where each element is vector ,
Second is Vector of size n where each element is vector
Hey, why didn't we use 2D-vector in place of this?
Creating array of vectors looks confusing.
Array of vectors takes lesser space!
@@takeUforward is it because of double the size property?
What if we define size of 2d-vector beforehand?
Something like below:
vector adjList(n+1, vector(m+1))
Only asking this because array of vectors was not so intuitive to me atleast :')
00:03 Learn how to represent a graph in C++ or Java
02:05 Learn how to store edges in a graph using an adjacency matrix or a list.
04:07 Creating an adjacency matrix to represent edges between nodes
06:09 Storing a graph using adjacency list takes less space than n square method
08:15 Adjacency list stores neighbors of a node
10:12 Using adjacency list for graph storage
12:22 Learned how to store graphs using adjacency list and matrix
14:13 Store weights in pairs instead of single integers
Crafted by Merlin AI.
understood.
at 6:40 the 2D array u made should be of size (n+1)X(n+1), u made it (n+1)X(m+1) by mistake
Understood Sir, Thank you very much
understood. Thank you
Thank you sir
great explanation ! loving this series!!💙💙💙
Is the adjacency list representation is same in Java or another could you please explain this in another video
Understood. Thanks a lot.
@takeUforward
how to solve if node is negatives??
like how you represents {(-1 --> 3),
Understood! Great explanation
Thanks a lot dear brother ❤❤ , understood fully
understood very well...
Great explanation
Understood Bhaiya 👍
just awesome pure gold
After filling the adjacent list with edges and weight the size of adjacent list is showing 0, why ? ( Code is given below and size is printed in line no. 8 ) thanks :)
// CODE FOR WEIGHTED GRAPH
1. int n,m;
2. cout > n;
4. cout > m;
6. vector adj[n+1];
7. for(int i=0; i u >> v;
cout > w;
adj[u].push_back({v, w});
adj[v].push_back({u,w});
}
8. cout
i started graph but still got confused in this 👇🏼
vector v[n] and vector v(n) are they same ??? 😭
exactly same
Thank you Bhaiya
understood bhaiya.
understoood!
understood, ty, u r the best
Happy teachers day
understood
2/56 done (3.12.22)
understood thank you 🙂
understood, thanks
tysm sir
understood ❤🔥
Understood !!
Awesome.....
Sir, apni face window ek corner me kr dijiye. That will be good.
understood sir🙏❤🙇♂
UNDERSTOOD!
understood striver :)
Understood.
awesome video
At 7:15 why is the matrix size [n+1][m+1] instead of [n+1][n+1]?
1 based indexing of graphs.
@@takeUforward I understand that, but why would the space taken by the matrix be O(nm) instead of O(n^2)?
@@thisisrajneel yes matrix size is [n+1][n+1] & SC O(n * n). IG it happened by mistake by him. it's okay.
please clarify striver @take u forward
@@astronomycosmology4888 It is a mistake only
understood!
Why did he remove all the leetcode links they were such a great help
what are we going to do if, in a graph, I have just two nodes and the value is 1 and 10^5 then we won't have the index 10^5 with us to fill!
UNDERSTOOD
You forgot to consider the space taken by the outer List while calculating total space in case of adjacency list
Total space complexity = V + 2E => O(V + E),
V space for an array of V vertices, each of which holds a vector,
2E (for undirected graphs), as each edge accounts for 2 list elements.
Understood...
😊
thank u
Understood 💥
understood!!
Best videos
incredible
understood❤
understood :)
Awesome!
6:00 island problem
Understood 😇
06:39 : it should be adj[n+1][n+1] instead of adj[n+1][m+1]
here we go