G-2. Graph Representation in C++ | Two Ways to Represent

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
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

Lets continue the habit of commenting “understood” if you got the entire video. Do follow me at Instagram: striver_79

[@raghvendrakhatri5848]

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.

[@nisha_k22]

@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

[@terrorwizard4055]

@@nisha_k22 You are right

[@BhavyaJain-qz8jg]

understood

[@raregem7995]

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.💛

[@user-ki5hf5sq4t]

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];

[@vikaskumaryadav3529]

I just wanted to say that u are pure gem for us and keep going the way you are going. Lots of thanks 🙏🙏

[@gokulbansal1038]

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

[@garvgoel1743]

yes... even I was thinking the same during the lecture

[@johnxina7496]

why n+1

[@satyampratap3808]

@@johnxina7496 Because of 1-based indexing, if you'll take it n then n-th node will not get added.

[@user-oy7ky9zk9l]

he also did a mistake of taking n+1 * m+1 it should be n+1 * n+1

[@vibhanshugarg3603]

the best explanation of graphs till now... thanks striver

[@mayank_rampuriya]

It would be better if we use *map m* rather than *vector v[n+1]*

[@Sameer-wx2pd]

Why bro

[@divyam-hx3ie]

@@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

[@MrAmitparida]

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; }

[@srianshumahadas7178]

At last, I was racking my head trying to understand how using vector we were able to represent a 2D matrix. Thanks, bro

[@MrAmitparida]

@@srianshumahadas7178 Welcome! int matrix[M][N] can be represented as vector matrix(M, vector(N)) .

[@cinime]

Understood! Great explanation as always, thank you very much!!

[@molyoxide8358]

from past 3-4 months I was running away from the graph but I got some hope after watching this video. 😍

[@udityakumar9875]

adjacency list is vectoradj. right? and not just 1d vector

[@rohithparepalli9237]

Yeah same doubt

[@shivgoyal103]

han bhai same doubt mera bhi .

[@ritabhsharma6627]

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

[@harsha4048]

​@@ritabhsharma6627🙌

[@VivekKumar-kf8yc]

@@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.

[@fuzi_blossom]

//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

[@tastaslim]

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.

[@GauravChaudharyNITW0501]

Best graph explanation🙌🏻🙌🏻

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@nbavideos4487]

Understood! Great explanation

[@rajkamalingle9144]

@7:16 Time complexity to store the adjacency matrix would be O(m) and not O(n)

[@shubhamsanodiya8368]

UnderStood Thanks for this amazing series

[@p38_amankuldeep75]

great explanation ! loving this series!!💙💙💙

[@ramanpareek5218]

Liked the video, notes taken, understood

[@itsmeakash_]

6:42 why is the matrix is [n+1][m+1] but previously u told [n+1][n+1]?

[@ArnabJhaYT]

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.

[@mahaprasadm9770]

I think it's a typing mistake.

[@ArnabJhaYT]

@@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.

[@dravitgupta7927]

@@ArnabJhaYT Got it👌.

[@aasthadubey3321]

@@ArnabJhaYT yes number of edges won't matter here

[@tasneemayham974]

I finished the ENTIRE dp series. THE BESSTTT. Now I am here for graphss!! Thank youu sooo much Striver!!!

[@harshitrautela6585]

do you suggest completing graph or dp series before?

[@tasneemayham974]

@@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.

[@Josuke217]

​@@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

[@tasneemayham974]

@@Josuke217 I don't know Babbar. But I know that once I learned recursion from Striver, I didn't need to open any other KZbin 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!! 😥😥😥

[@Josuke217]

@@tasneemayham974 thanks , is the recursion series complete? Because someone told me striver has skipped some topics.

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@Sarkar.editsz]

Thanks a lot dear brother ❤❤ , understood fully

[@sukhpreetsingh5200]

just awesome pure gold

[@user-bt6mh9ez3u]

Awesome Video..understood everything

[@mriduljain6809]

Understood Bhaiya We can also use this for representing adjacency list: unordered_map list

[@ronakslibrary8635]

US , Excited for learning graph

[@dhivyashri6554]

understood, ty, u r the best

[@subhamoybera6456]

Great explanation

[@PRALAY.THAKUR]

very nice explanation

[@rishabhgupta9846]

great explanation

[@vikasbagri1225]

understood very well...

[@ashishparmar762]

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.

[@samuelfrank1369]

Understood. Thanks a lot.

[@DevashishJose]

understood. Thank you

[@bhavkushwaha]

Thankyou Striver, Understood!

[@KapilMaan-vw9sd]

amazing video sir ji

[@VarunKaushal-zx9zq]

Thank you so much

[@morganyu3391]

Understood Bhaiya 👍

[@shubhamsukum]

vector adj[n+1]; means => vector adj(n+1); Correct me if I am wrong?

[@viz_dugz]

something i got stuck on myself, didn't notice the square brackets

[@tanishgupta7879]

it's a vector of array. Try to read it from right to left. At each index there is an empty vector.

[@shrutikahilale]

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.

[@DevanshuAugusty]

@@tanishgupta7879 you mean array of vectors

[@fmkhandwala39]

understoood!

[@shyren_more]

understood, thanks

[@ashitasrivastava681]

UNDERSTOOD!

[@akhirulislam4079]

I feel the matrix should be like adj[n+1][n+1] not adj[n+1][m+1]

[@vishvrajbaan6634]

yes this right

[@ProSol-im6zn]

Can u say How do u know those matrix

[@ProSol-im6zn]

I don't have a proper idea about adj[n+1]

[@Arkagame19]

Ya I wasss about to comment this

[@SsjRose26]

​@@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

[@ANURAGSINGH-nl2ll]

understood thank you 🙂

[@abhaysinghchauhan4521]

Understood!

[@sadiashafaque3517]

Awesome!

[@_hulk748]

understood sir🙏❤🙇‍♂

[@UECAshutoshKumar]

Thank you sir

[@niyamaliyakkal]

understood ❤‍🔥

[@niteshsaxena1066]

awesome video

[@DevanshuAugusty]

15:20 so for this it would be: vector adj[n+1] .... right?

[@vivek03501]

no it should be vector adj(n+1);

[@vani.sharmaa]

vector adj[n+1] basically means a vector of arrays right? so can we also declare it as vector of vectors?

[@mohakhiphop]

Yes, which is adjacency matrix but it takes more space

[@mohakhiphop]

@@rahulshah2685 no its right , vector[] is array of vector i.e. 2 d array

[@DevanshuAugusty]

@@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.

[@mohakhiphop]

@@DevanshuAugusty yep true💯

[@careerwithmann481]

understood bhaiya.

[@sarangkumarsingh7901]

Awesome.....

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@mathematics7746]

incredible

[@deepakbhallavi1612]

Understood 💥

[@divyanshbhatt8273]

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!

[@suhaanbhandary4009]

understood!!

[@atulkohar6959]

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

[@khechraay]

bro he is using array of vectors `vector adj[n+1]`

[@slemanabbas7720]

I am very lucky because I found you❤🎉🎉

[@AbhishekThakur-gz6ul]

Understood ☺️😄

[@siddheshborse3536]

Understood... 😊

[@user-sp9rg7if3i]

@takeUforward how to solve if node is negatives?? like how you represents {(-1 --> 3),

[@KartikeyTT]

tysm sir

[@shresthbhakta7337]

Understoood!!!!

[@nasimnajand9697]

Thanks in advance

[@suryakiran2970]

understood❤

[@vaibhav8257]

understood!

[@ashwanisingh3291]

Understood 😇

[@ripanroy8399]

Understood!!

[@nathonluke4058]

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.♥️♥️♥️

[@shantohossain1372]

his explanition is the worst ever, kunals, shardha didis explination is far better than his

[@worthlessguy1621]

understood striver :)

[@prakhargarg4166]

Best videos

[@sujalgupta6100]

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 .

[@takeUforward]

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.

[@lakeshkumar1252]

UNDERSTOOD

[@akshatshrivastava7273]

understood.

[@karthikavijayannv5319]

understood

[@arihantjain3274]

Understood

[@oqant0424]

2/56 done (3.12.22)

[@varunkumar-vs5wc]

thank u

[@sairammurthy6121]

understood :)

[@TON-108]

i started graph but still got confused in this 👇🏼 vector v[n] and vector v(n) are they same ??? 😭

[@phoenix_1_3]

Understood

[@valendradangi1822]

Bhiya at 7:10 adjacency matrix should be of (n+1)*(n+1) size and not (n+1)*(m+1).

[@DevashishJose]

Understood.

[@akkisharma7552]

Happy teachers day

[@animestan265]

Got it

[@sumitkanth5349]

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

[@avanishmaurya2034]

Nice

[@mathematics7746]

awsmmmmmmmm

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@111rhishishranjan2]

can anyone tell me what does one way indexing mean

[@ssbcodes2654]

Hey, why didn't we use 2D-vector in place of this? Creating array of vectors looks confusing.

[@takeUforward]

Array of vectors takes lesser space!

[@ssbcodes2654]

@@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 :')

[@al_ted]

understood ...

[@udaypratapsingh8923]

here we go

[@rahulr9301]

can anyone please explain me what is zero bases and 1 based node??

[@akashsahu2571]

yes