G-2. Graph Representation in C++ | Two Ways to Represent
Вставка
- Опубліковано 4 сер 2022
- Notes Link: takeuforward.org/graph/graph-...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------
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
I just wanted to say that u are pure gem for us and keep going the way you are going. Lots of thanks 🙏🙏
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];
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
from past 3-4 months I was running away from the graph but I got some hope after watching this video. 😍
Understood! Great explanation as always, thank you very much!!
It would be better if we use *map m* rather than *vector v[n+1]*
Why bro
@@Sameer-wx2pd 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
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)) .
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.
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 UA-cam 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.
Thank you, Striver 🙂
great explanation ! loving this series!!💙💙💙
Liked the video, notes taken, understood
Best graph explanation🙌🏻🙌🏻
Understood! Great explanation
UnderStood Thanks for this amazing series
//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
US , Excited for learning graph
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.
just awesome pure gold
Thanks a lot dear brother ❤❤ , understood fully
Understood Sir, Thank you very much
Awesome Video..understood everything
@7:16 Time complexity to store the adjacency matrix would be O(m) and not O(n)
Thankyou Striver, Understood!
Understood Bhaiya
We can also use this for representing adjacency list:
unordered_map list
understood, ty, u r the best
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 👍
Understood. Thanks a lot.
Great explanation
understood. Thank you
very nice explanation
understood very well...
great explanation
UNDERSTOOD!
Thank you so much
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
understoood!
understood, thanks
Understood!
understood bhaiya.
understood thank you 🙂
Awesome!
understood ❤🔥
understood sir🙏❤🙇♂
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.
Understood 💥
awesome video
Thank you sir
incredible
Thank you Bhaiya
Understood ☺️😄
understood!!
tysm sir
Understood...
😊
Understood 😇
Understoood!!!!
2/56 done (3.12.22)
Thanks in advance
UNDERSTOOD
understood❤
understood!
understood striver :)
understood.
15:20 so for this it would be: vector adj[n+1] .... right?
no it should be vector adj(n+1);
@takeUforward
how to solve if node is negatives??
like how you represents {(-1 --> 3),
understood
Understood!!
Best videos
understood :)
Understood
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💯
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 am very lucky because I found you❤🎉🎉
Understood
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
thank u
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!
Thank you very much. You are a genius.
here we go
Understood.
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.
Nice
Happy teachers day
awsmmmmmmmm
Understood👍
understood ...
can anyone tell me what does one way indexing mean
can anyone please explain me what is zero bases and 1 based node??
does this playlist also contains trees?
Bhiya at 7:10 adjacency matrix should be of (n+1)*(n+1) size and not (n+1)*(m+1).
Bhaiya itna deep kisi ne nhi samjhaya "Understood😉" Maja aa gaya
wtf
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 :')
Got it
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
i started graph but still got confused in this 👇🏼
vector v[n] and vector v(n) are they same ??? 😭
he teach well