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];
@@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 RUclips 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!! 😥😥😥
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; }
@@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
//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
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
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.
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.
@@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
@@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.
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
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.
@@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.
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 [ ].
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.♥️♥️♥️
@@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 :')
Thank you for sharing. However, it seems the statement m can be 'anything' is incorrect. There is an upper limit to m, which is P(n, 2) (in the case of a directed graph)
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 believe we can use mod to convert it to positive index and use pair where we can create a bit to show if nod is negative or positive just like we did to store weights of edges
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
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
Yeah thanks. I was a bit confused too.
how space complexity is 0(2e) in list as we also have to count space for the array made to store the list
@@anshakki7838 vector is a dynamic array , so initially its size will be zero, and grows only when you push_back something
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];
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 RUclips 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.
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)) .
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
yeah even i thought of the same , does vector v[n+1] work well for code? please answer
@@POTNURURAHULADITHYA Yes it works well in code. vector a[n] is just an "array of vectors". Pretty much the same thing as "vector a"
the best explanation of graphs till now... thanks striver
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 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. 😍
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.
@7:16 Time complexity to store the adjacency matrix would be O(m) and not O(n)
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.
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.
15:20 so for this it would be: vector adj[n+1] .... right?
no it should be vector adj(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
Understood Bhaiya
We can also use this for representing adjacency list:
unordered_map list
7:20 dimensions of matrix should be n+1, n+1
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
Bhiya at 7:10 adjacency matrix should be of (n+1)*(n+1) size and not (n+1)*(m+1).
thank u so much striver. amazing video
Take you forward rocks, amazing video:)
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]`
@@khechraaycould you please elaborate
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
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💯
Thank you, Striver 🙂
UnderStood Thanks for this amazing series
Bhaiya itna deep kisi ne nhi samjhaya "Understood😉" Maja aa gaya
Understood! Great explanation as always, thank you very much!!
Liked the video, notes taken, understood
"UNDERSTOOD BHAIYA!!"
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.
US , Excited for learning graph
Best graph explanation🙌🏻🙌🏻
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
Lecture successfully completed on 02/12/2024 🔥🔥
I am very lucky because I found you❤🎉🎉
Thankyou Striver, Understood!
I love this, what a tutotial.
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
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
06:39 : it should be adj[n+1][n+1] instead of adj[n+1][m+1]
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
very nice explanation
Awesome Video..understood everything
great explanation ! loving this series!!💙💙💙
Great content and explanation
Shouldnt the size of adj in 6.57 be [n+1][n+1] instead of [n+1][m+1] ?
yes
i started graph but still got confused in this 👇🏼
vector v[n] and vector v(n) are they same ??? 😭
exactly same
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 :')
Understood! Great explanation
found this graph series playlist late🙁
Understood Sir, Thank you very much
Understood Bhaiya 👍
Thanks a lot dear brother ❤❤ , understood fully
Thank you for sharing. However, it seems the statement m can be 'anything' is incorrect. There is an upper limit to m, which is P(n, 2) (in the case of a directed graph)
Heyy striver you had done mistake in definig the code for adjacent matrix as @6:43
As there are n nodes so it will have a matrix for nXn
very great explaination
Done. Thank you so much!!
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
@3:14 m can't be anything, in a dense graph : m = (n * (n-1))/2
amazing video sir ji
just awesome pure gold
6:00 island problem
Happy teachers day
can you show graph representation in Python too? Like in upcoming videos? for beginners.
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 sir🙏❤🙇♂
Is the adjacency list representation is same in Java or another could you please explain this in another video
great explanation
understood, ty, u r the best
Understood. Thanks a lot.
understood bhaiya.
@takeUforward
how to solve if node is negatives??
like how you represents {(-1 --> 3),
i believe we can use mod to convert it to positive index and use pair where we can create a bit to show if nod is negative or positive just like we did to store weights of edges
6:31
adj[n+1][n+1];
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
understood very well...
understood thank you 🙂
Why did he remove all the leetcode links they were such a great help
i hope this like button is recursive for u man
UNDERSTOOD!
understood. Thank you
Understood 💥
Sir, apni face window ek corner me kr dijiye. That will be good.
understood striver :)
Thank you Bhaiya
Understood!
This channel aldready had graphs playlist right.....why striver is repeating again?
Community post!
can anyone please explain me what is zero bases and 1 based node??
awesome video
Content writing internship k liye apply Kiya hai... Ha na kuch to bata dijiye
Understood ☺️😄
UNDERDTOOD !!
understood ❤🔥
Thank you sir
Thank you very much. You are a genius.
does this playlist also contains trees?
2/56 done (3.12.22)
Understood...
😊
Thank you so much