L 1 | Graphs by Striver | Concept Decoding and Problem Solving | Graphs Master Class

oh what's up guys am i audible as i'm audible uh okay 500 plus oh 500 audible sorry 500 man this is crazy omg this isn't a resignation video it's a graph video so i am not expecting so many people to be like but i welcome to the stream guys welcome to the uh stream we're gonna do some serious stuff in the next seven days he gets seven days so before before starting let's quickly wrap up let's quickly wrap up with the introduction so for everyone who's new out here and who doesn't know me let me introduce you myself my name is raj vikramaditya i'm known as strava in the programming community i'm a competitive programmer i am currently working as a software engineer i'm a candidate master at code forces a sixth hour at code chef i have been teaching from the past couple of years and i also run a youtube channel where i have one lakh plus subscribers the subscribers that i have gained by teaching and teaching only no clickbait stuffs and the subjects that i take are competitive programming data structure algorithm c plus plus interview preparation and you can definitely use my coupon codes driver in order to get 10 percent uh discount on the unacademy plus subscription now there is something which is known as reliable now what is this available now you must be applying to companies right but you don't get you don't get opportunities or you don't get a call back a reliable is a platform where you can directly apply to the company by just giving a hiring test now you don't need to have a degree if you have skills that is something which uh available once so you uh so let me just tell you it's basically india's first test hiring platform where you go give a test you get a specific score using that score you can apply it to around i think 55 500 50 plus 50 plus startups including cred razor pay coordination 1mg urbanclap and many more now there are a thousand plus job openings specifically for three positions business development front-end development back-end development so you can just attempt this test and go and apply now registering in reliable is very very easy you can just go and sign up give the test and then you will get the interview scheduled and after that you will be hired so go ahead and check out reliable and you can book slots as per your choice there is nothing special okay and once you get your score you can create a video resume which will be visible to all the recruiters so please make sure you register for reliable if you haven't joined the telegram group of this particular community please make sure you join that out and write it down if you're new to this channel do consider subscribing hit that subscribe button hit that hit that subscribe button and uh like like the stream like a thousand likes thousand likes as a target so yeah uh we're gonna teach on ipad i hope that's okay to everyone uh let me know with the ipad visible visible level is free reliable is free guys reliable is free we're breaking records man 500 on a live stream for teaching that's that's crazy that's some crazy man okay let's go let's get started so how many of you know how many of you know no spamming let's get started and let me tell you what was the content for the seven days seven days how is this different from the series that is uploaded at my channel and everything else i'm gonna tell you so day one will be where i'll be telling you graph and representations graph and representation is what i will be telling you okay next we will be uh talking about the traversal techniques right after that i will be telling you uh like cycle detection techniques so remember in traversal there is one specific traversal which is known as bfs now this bfs is asked a lot in amazon yes like amazon microsoft google uh they keep on asking this particular algorithm bfs so i'm gonna solve around three problems okay so in traversal specifically on bfs i'm gonna solve three problems and there is another one dfs over here i'll be solving a couple of problems okay and those problems will be graphs but it will be on matrix so that you can visualize how a matrix can be visualized as graph because that is what uh i will be planning for today that's for day one going forward in day two like tomorrow we can discuss without wasting time are you guys ready it ready okay let's get started what's a graph it's a very important uh data structure first of all now where is this graph used uh google maps is one of the primary examples google maps is one of the primary examples so you would have seen ticket again uh you would have seen google maps right now how how do you like you give the source and you get the destination right so the google map tells you the shortest distance nowadays uh in terms of time and also it gives you an option in terms of all the other options so have you ever wondered how this google maps work so generally google map works in terms of like it uses internally graphs and all the other data structures to figure out what is the shortest distance and it shows you that particular short resistance a lot of algorithms that are being implemented so specific like the use case that is always visible to you of graph is google maps something like that is being used by what i got please uh just a quick uh request to everyone since i'm starting to teach don't deviate me by commenting weird comments i don't want any any controversies any random of topics let's focus two hours we are gonna focus and today let's make sure when you go back you will be having a lot of stuffs okay so if anyone is spamming out please that's your responsibility to stop him okay there's no need to quote today will be like when i reach to bfs then you can code okay so in graphs uh there are couple of things one is the nodes or generally it's known as the vertex okay notes of vertex and edges okay so what's a node what's a node so in graph if i draw something like this this is let's draw something like this okay if i draw something like this you generally call this guy as the node these are notes okay like if i just uh tell you that the this is node one is a node two is a node three is a node ticker uh these things are nodes and you can also call them as vertexes okay now what are these things these are edges these are known as edges okay now what i'll say is for this particular graph yes for this particular graph i can say that there are three nodes and three edges now is there a particular relation is there a particular relation that if there are so many nodes there has to be so many edges no there is absolutely no particular relation you can have any number of nodes you can have any number of edges there is nothing like it okay so that's the specialty of graph you can have any number of edges like probably you can have uh like if i just give you an example you can have something like if i take a graph like this like you can have something like this also where you see the number of nodes of four the number of edges are six so it's not necessary that the graph can have like it's necessary it's not necessary that the edges has to be interlinked with the number of notes that is something which you have to be that is something which you have to be like sure so that's something uh now critical thing has the graph to be connected like we'll come to that on specifics but as of now let's understand this is a graph now if i just give you a structure where i say 1 2 3 and then i say 4 5 you will also call this as a graph this will be called as a connected graph remember this this will be called as a connected graph whereas this will be called as a disconnected graph remember this this is a disconnected whereas this is a connected graph always remember this it's not necessary that all the notes of a graph has to be connected it might not be they might be in though though different planets maybe it's okay it's okay okay so coming across now what kind of graphs are there now there can be graphs like directed so let's understand what is a directed graph uh you have to clear for people who are wanting to enjoy the stream full screen comments make it a full screen you'll not see the comments okay make okay so no not two graphs it's not two graphs it's a graph with two components it's a graph with two components okay now over here over here if i just erase this if i just erase this then i'll say it's a graph width this is a component this is a component and this is a component so there are two components got it this is a component and this is a component it's okay it's you should not single graph you can save multiple components don't don't it's it's never like a teen graph diy yeah three components can be given to you four components can be given to you but in a question they will never say components components okay so what's a directed graph till now i did draw graphs which did not have any direction of edges like like if i call this there is an edge between two to three there's an edge between two through three but uh can you say me can you see me yeah is it from two to three or is it from three to two like what do you think where is the edge from is it from two to three or from three to two you're not sure are you sure i don't think you're sure so this is something which is known as undirected edge undirected edge remember the term it's known as undirected edge okay where you can move from two to three like you can move from two to three as well as three to two like there is no direction if there is no direction you can move from two to three and from three to two so it is something which is known as a undirected graph it is something which is known as undirected graph got it now whenever i say directed graph whenever i say directed graph this can be an example of directed graph yeah it's a tree it's a tree kind of a data structure but you can still call it as a directed graph as i said it's not necessary that the number of components and the number of nodes or they need to form a cycle as long as there are nodes and they're connected by edges you can tell them as a graph okay like in the un undirected graph even this this is a tree data structure this is a tree data structure but you can also call this as a graph it's okay if you call this as a graph because these guys are notes these guys are nodes nodes nodes nodes and these guys are edges these guys are edges so you have nodes you have edges what that here a tree can be a graph a tree can be a graph remember this a tree can be a graph but a graph cannot be like all graphs are not tree a tree is a graph but all graphs are not tree remember this can a single graph yes it might contain it might contain uh is asking can a single graph contain both directed edge and yes it might contain every tree is a graph whereas a graph is not a tree okay okay directed graph this is a directed graph now someone did ask me a question is it necessary like i can also represent it and i can also represent a undirected graph by a directed graph how let's assume this is an undirected graph okay let's assume this is an undirected graph how can i represent this as a directed graph it's very simple you write one you write two you write three and you say okay one to two two two one yeah you can draw two edges now can i say this is a directed graph can i say both are same yeah this this is a this is a undirected whereas this is a directed is the concept clear is the concept here a undirected graph can also be represented in a directed graph is this clear every tree has a property which since i'm teaching graphs i'm not teaching every tree has a property the property is if there are n nodes then the number of edges will always be n minus 1 remember this every tree has this property every tree has this property like if you see if this is a tree it has three nodes and two edges every tree has a property it has n nodes and n minus one edges in graphs this property is not seen as i said there is no relation between nodes and edges there can be any number of nodes there can be any number of edges okay tree is a undirected graph a tree is an undirected graph unless someone specifically mentions your key there is only an edge directed from this to this then you call it as a directed tree in most of the cases we deal with undirected trees like normal tree in grass also in most of the cases we will be dealing with undirected graph but in some cases we will be dealing with the directed graph clear is that clear yes yes also dharma there can be any number of edges between this it's not necessary you will only have two edges it's not necessary that you will only have two edges i can also draw like this i can also draw like this one two this this there can be any infinite number of edges between two guys any infinite number of edges between two guys if don't focus on code i will be i'll be telling you in such a way that you can understand in java and c plus plus doesn't matter my teaching style is something very different where i don't focus on languages okay we are not doing trial question if there are two nodes and have two edges no you cannot that is why it cannot be remember a tree means tree is very different see a tree is a data structure which is something like this on it there is only a single edge between two nodes in a tree there is a single edge between two nodes in graphs there can be multiple edges there can be any no relation it can be anything but entry there will only be a single edge between two notes remember this don't complicate stuffs don't complicate stuffs i always say don't complicate stuffs usually what happens with all of you people are you know like complicating the easier stuffs and then you mess up a lot don't complicate keep it simple the simple definition is there are two kinds of graph undirected and directed the undirected graph means no direction of edges directed means direction of edges as simple as that no relation between nodes and edges got it i guess so much okay let's let's move across what is a weighted graph let's understand what is a weighted graph now when i say what's a weighted graph let's understand the meaning of weighted graph now weighted graph is something when i say that hey this is the graph okay and assume these are the uh node suites okay these are the graphs and these are the node weights so what i'm saying is sorry edge weights so what i'm saying is this a edge is having a weight of one i'm saying this edge is having a weight of two i'm saying that this edge is having a weight of two this edge is having a weight of three you can correlate this yes you can correlate this to a google map right you can correlate this to a google map for an example i say kolkata is a node if you go from kolkata to let's say mumbai the distance is probably one five six seven kilometers i'm just guessing from mumbai to goa the distance is probably something like 300 kilometers from mumbai to pune so these are you can just correlate right you can correlate right as a graph so these are the weighted graph assume 200 kilometers it's a weighted graph with distances so weighted graph clearer weighted concept here a weighted graph whenever i attach i whenever i attach a weight to an edge i call it as a weighted graph whenever i attach a weight to the edge i call it as a weighted graph here got it okay guys don't ask silly doubts that is what i'm asking i know none of the doubts are silly but they are asking doubts focus on whatever i'm teaching then you can go back home you can do your research and if you have still doubts you can use the telegram community to discuss there are people who will answer you okay okay now this is undirected no in google maps it's undirected queue kolkata say you can go to mumbai as well and from mumbai you can come to kolkata as well so it's an unrelated graph right directed graphs are basically those things those are directed graphs those can be called as directed examples of real life right okay let's move okay let's move now c plus plus java i will not be focusing on c plus java i'll be writing sudo code i will be writing sudo code so as of now can you tell me how many c plus plus users are there and java users how many as i said weighted graph can be anything you whenever you attach and weight to an edge be directed be it undirected it is called weighted graph you can call it as weighted directed graph you can call it as weighted undirected graph anything you can call it okay c plus plus java java okay anything so if you're learning if you're learning graphs you should not be complaining whether it is c plus plus or java no complaints whether you're learning c plus plus a complaining energy okay pseudocode so first thing that i have to explain you is representation of graphs it's very important because if you're solving a problem unless and until you store the graph in some data structure how will you solve the problem so the first way the first way is to create a 2d matrix both in c plus present in java i hope you know how to create a 2d matrix in 2d matrix its guess got it 2d matrix is something which is known as adjacency remember this adjacency matrix it's a very important term it's a very important term remember this in your head forever adjacency matrix now generally how is the input given to you how's the input given to you so let's take an example of the graph so i'll draw a mini graph over here assume i'm drawing an undirected graph as of now assume i'm drawing a mini graph like this okay assume i'm drawing a mini graph like this so generally the input the input pattern in all the questions in competitive programming in lead code in all everywhere like everywhere like in coding rounds the input pattern will always tell you will always tell you the number of nodes so over here the number of nodes are four right and the number of edges the number of edges are four so always the first line will contain the number of nodes which is definitely n and the number of edges which we can call it as m n and m next will always follow m lines we will always follow m lines what i am discussing as of now is the input pattern for a graph next will always follow m lines now what will these m lines contain i am seeing that there is an edge between one is to two i am seeing that there is an edge between one is to two so what i will do is i will say there is an edge between one is to two so that's the first stage that i'm saying next i'm seeing there's an edge between two is two three next i'm saying there's an edge between one is to four next i'm saying there is an edge between three is to four now before you have any doubts these edges there are four edges one two three four they will always give you four edges they will always give you four edges it's not necessary that the four edges will be given in certain order it can be any order probably three four can appear first one two can appear after that it can be in any order the input the edges can be in any order okay that's the first thing the next thing is there is an edge between 1 is to 2 so if 1 2 is given it's ok they can also give you as 2 1 that's also okay as long as they are saying you it's an undirected graph it absolutely doesn't matter whether the edge is between 1 is to 2 or is from 2s to 1 make sense this is how the input will be given to you this is how the input will be given to you clearly understanding the input is very important generally in arrays generally in arrays they tell you i'll give you an n and then i'll give you n integers array input is like this now an input is like n then i'll give you n integers right so in graph the input pattern is like this is it clear i have i've cleared all the doubts i've cleared all the doubts about order i have cleared all the doubts like it can be one two two one anything clearer wait wait yes as of now i'm explaining you undirected graph represent undated graphs we are representing undirected graphs then i'll teach you representing directed graphs then i'll teach you representing weighted directed class don't worry don't worry again just wait let me teach let me teach okay so let's uh so just erase and tell you how's the store i know a lot of you have a lot of lot of idea about these things but you need to understand there is an audience who is watching so they might not be knowing all the things so i have to tell all the things isn't it okay so what happens is you create basically a matrix and this matrix is of the size of the notes now remember these nodes can be one based or can be zero based it's very important over here we have taken one based over here i have taken one base but the graph can also be given as zero based but in almost all the problems in code forces in lead code they will never give you a graph like this this is my assurance to you they will never give you a graph like this 3 4 10 12 this kind of graph you'll never see there is a sequence like one two three four yoga notes the node numbering is generally one two three four other if you see a sequence like three four ten twelve and one two all these things are missing then the problem uh setter and it provides someone again got it so we have taken one beast so if you have taken one base indexing what you'll do is you will create a n plus one into n plus one matrix so n plus 1 into n plus 1 matrix let's create that so n plus 1 into n plus 1 matrix is created okay now what i'm saying is there is an edge between one is to two there is an edge between one is to two so what you will do is you will go to one and you will say hey hey one on your two there is an edge still mark it you will mark it okay so this is done next you will say that there is two and three it will go to two and it'll go to three unit market so two and three is also done next you'll go to one is to four so you'll go to one and you'll go to four and you'll mark it okay so uh this is just a quick one let's reiterate if there is one and two you will go to one and you'll go to two and mark it one and two you'll mark and the opposite two because it's an undirected edge undirected soul typical naga vulta is two and one perfect next there is two and three so from two to three from two to three and ulta three to two three to two so this is also done one four one four means from one to four one to four and from four to one from four to one perfect three four means from three to four and from four to three three to four and from four to three so the graph the adjacency matrix the adjacency matrix represents the edges if if you see over here there is an edge means four and zero or zero yeah is zero yeah one pivot there should have been at one this should have been what one they should have been at one sorry guys this should have been at one so yeah i can easily say that if there is a tick over here four and one there is an edge four and one there is an edge understood the logic have you understood the logic understood as long as i can give my emotions to you i'm okay so is this clear how do you do this it's very simple it's very simple so if you're writing alright pseudocode i'll not use sublime text because we have c plus plus and java users and python two so i'll not use sublime text so it's very simple you will take input of n and m input of m and then there will be images so you will just i trade from one is to m and there is uh input of u and input of v basically there are m edges that are given to you basically there are images that are given to you so what you'll do is you will create an adjacency matrix of n plus 1 n plus 1 okay and then you can be like adjacency of uv equal to 1 adjacency of v u equal to one clearer storing clear is the storing clear okay as a clear over so what's the time complexity uh we're using normal big of m but the problem that we are having is the space complexity we are using big o of n cross n for m edges which is a lot because there are hardly images there is hardly images if you carefully observe there are images but the space that you're ending up using is somewhere around b go of n cross m like near about b go of n cross m so this is a problem remember this you you can only use adjacency matrix if the value of n is very small n is small then use forget my handwriting like i'm writing a channel but miranda and writing my writing is like this only okay now i'm not talking about loop i'm talking about space complexity i'm talking about space complexity guys this is space complexity sc space complexity clearance got it got it why n plus one because it's a one based indexing now it's a one based indexing so if you're wanting to mark four if you're wanting to mark four the index four will only be present the index four will only be present if you declare an n plus one because n was maximum of four you have to declare one more clear got it okay so mean like if you're watching graphs if you don't know space complexity don't watch graphs graphs is for people who are well versed with precaution i'm again repeating please please please if you are if you are very new don't watch it graph is a data structure which is learned after you have spent around some time with your data structure algorithms okay you know what is a stack you know what is the queue you know what is time complexity you know what is space complexity you know what is one base indexing so i will request you if you do not know what is the one based indexing if you do not know what is stack what is array is what is uh this 2d matrix please don't watch because then you will go and trust me graph is not for people who are like i hope you understand what i'm meaning to say right please prerequisites are please re-question see if you don't know the question please leave the class as of now i don't want someone to go and say somewhere but the recursion is the prerequisite time complexity space complexity queue priority queue foreign if people ask why n plus one how will i teach man if people ask why n plus one will i teach i told you know why one one four i can draw an edge from one to four as well as opposite four to one someone asked it's very tough to manage an audience of 750 around life i hope you need to understand this okay so the space complexity that we see is well let me tell you this is for extreme loops if you're feeling this is going slow you can watch the graph uh playlist on my channel when was the graph playlist on my channel because whatever i teach today you'll find that on my channel if you if you're thinking it's a wastage of time you can go and watch that it'll be quick for you so the adjacency list is taking a lot of time adjacency list is taking a lot of time so what we will decide is okay let's do one thing the graph was like this right the graph was like this so what i have decided is uh today what i have decided is listen uh let's take adjacency list spelling ignore the spelling what's this adjacency list it's basically an array now i'll tell you what does that mean whenever you define int of array of 10 what does this mean a array of size 10 is created where every index is storing an integer right this means an array of size 10 is created where every integer like every every index is storing an integer so if you declare like this can i tell you what does this mean what does this mean you are declaring an array of size five remember this you are declaring an array of size 5 where at every index a vector is stored where at every index a vector is stored okay now c java people java people can use array list integer array equal to new error list like over here over here instead of integer you can use arraylist of arraylist okay java people can use arraylist of arraylist right or you can create an arraylist array so in c plus plus it's a vector int of array list of array list of array in java also you can create arraylist of array okay add a list of arrow list of array whatever you want to create so what do you usually do is let's understand what do you usually do vector int array 10 or in this case area 5 so what happens is what happens is an array is created remember this an array is created 0 index first index second index third index fourth index a five size array is created and at every index there is an empty vector there is an empty vector at every index at every index that there is an empty vector again i'll be the moment someone comes up and says hey listen there is an edge between one is to do the moment someone comes up and says hey listen there is an edge between one is to two so what you will do is you will go and say hey one you had an empty vector now you had an empty vector now why don't you put two into your empty vector remember okay i don't have an issue this signifies this signifies that the node one that the node one has an adjacent node of two this signifies that the node one had an adjacent node of two okay so we know that if there is an edge between one is to two we know that if there is an edge between one is to two which means there is an edge between two to one so what you will do is you also go to two and say hey you also had an empty vector no why don't you take one perfect so this is how you can store it next if there is an edge between two to three can we do the same thing hey two can you store three like okay hey three can you store uh two like yes i can so we stored that perfect next edge is between three to four i'll do the same thing hey three can you store four okay hey four can you store three perfect next there's an edge between four is to one okay so i will say hey four can you store one you're like okay hey one can you store four i'll be like okay so can i say ultimately at the end of the day this is how your adjacency list looks like can i say at the end of the day this is how your adjacency list will look like do you agree well at the index 1 where at the index 1 there is a vector of this index 2 there is a vector of this index 3 there is a vector of this index 4 there is a vector of this do you understand this the graph can be zero based indexing can be one based indexing over here it's a one based indexing got it right clear it now how do you take the input i will try to address lesser doubts so if you take i equal to similarly you can take input of input of u input of v similar and if you run from one to m so input of u input of v what's u and v what's u and v u is this v is this u is this v is this u is this v is this so you run basically input of u and v the next step that you'll do is use the adjacency of u adjacency of u so basically you're saying hey hey one he won one adjacency u means the vector adjacency u means the vector whenever you declare int array of ten and you write yes and you write array of 2 what does that gives that gives you an integer right so if you have declared vector of int of array of 10 and you say something like array of u what does that mean it means a vector so on that vector you are saying hey can you please add v that's okay similarly you can say hey adjacency of v can you please add you so in this way you can create the entire adjacency list in this way you can create the entire adjacency list does that make sense to everyone right so you can use the uh push back it's sublime problem if you see java so similarly in arraylist if you're using java this dot add this dot add if you're using java you can use dot add dot okay we will use sublime text don't worry a smaller code we will not use sublime text okay got it okay now what's the space complexity now is the space complexity the space complexity in the adjacent matrix was n into n what's the space complexity here let's assume so one two three four five six seven eight so can i say i took an eight space can i say i took an eight space logically i took an eight space that is logical so generic on a generic version you're creating n places right on generic you're creating eight n places n places create the room you're creating an n size so n for every edge for every edge whatever you're doing you're inserting two guys for one you're inserting two for two you're inserting one so there are two elements inserted so can i say that the space complexity used will be b go of n plus 2 m big o of n plus 2 m in case of undirected graphs in case of undirected graphs it will be big o of n plus 2m y n i repeat because array of size 5 for that n y 2 m because if there is an edge between 1 is to 2 1 contains 2 2 contains 1 that's why what i'm doing is i'm saying n plus 2 m got this is this clear why it is n plus 2 m i hope that's clear i hope that's clear now a critical junction is over here a critical portion using adjacency of u dot push back of v adjacency of u dot pushback of v why are you doing v and u because it's an undirected graph so if it's a directed graph what will you do if it's a directed graph what will you do are there a directed graph you cannot call it 2m why because assume assume there are other places which are empty you cannot call it exactly 2m because there might be other places which are empty it's not necessary every guy hasn't if i give you single components if i give you single components like single nodes then there will be a problem right so to be safer side you'll call it n plus 2f again it's not exactly because a lot of times you're not using up spaces but yeah i hope you understand yes so if you are doing a directed graph in case of directed graph this will go off in case of directed graph this will go off this is go off in case of directed graph no required okay now so you have understood how to store an undated graph you have also understood how to store a directed graph everyone has understood now what we will do is yes what we will do is we will try to uh how to store big of n plus m yeah you can call it as near about remember going forward i will not be writing this i will always be calling this as big o of n because it's near about that i can call it as big o of n so in computative programming or any other you can call it as big o of n okay remember this okay how to store weighted graphs that's very important so how to store weighted graphs very very important it's a very important candidate how will you store i listed the weighted graphs obviously use adjacency list because adjacency matrix takes a lot of time right how to store weighted drive how to store weighted graphs so the format will change the problem with uh with students is they don't know uh to write a recursive function they're expecting they will learn graphs this is where the problem lies and when will they get tougher yep sequence wise followers so you can take n you can take m now the m lines will be there will be m lines and those m lines will contain u v w w where w is the weight where w is the weight so what you will do is over here you will like vector of pair vector of pair vector of pair is what you will declare okay now instead of storing one element you will say there are multiple elements for an example if i take 1 is to 2 and i say the weight is 1 if i write 3 and i say weight is 2 and if i write 4 like if this is these are the weights so the adjacency list will be something like this zero one two three okay and then uh there are like one two one so for one two one so one will say i'm going to store two and the weight is one two will say i'm going to store one and the weight is one okay perfect next two three two so in two you'll say hey three you have an edge weight of two three you have an edge weight of two and two next three one four one three four so you will say hey one you have a three with a weight four right hey three you have a one with a weight four so that is how you can do it right got this how do you store it's basically a pair it's basically a pair that you'll do it's basically a pair that you will do here in order to store adjacency list you have to do a pair in order to store an adjacency list nothing different okay clearly okay so code adjacency of u dot pushback i'm writing as pb pair will be v w and adjacency of v dot pushback uw that's the only change in code what to store directed graphs like sorry to store weighted graphs so everyone uh now knows how to store data structures everyone now knows how to store data structures right what can i do jeta what can i do there is a mix of audience there's a mix of audience i cannot help now they go sub nice host problem no weighted graph can be anything weighted graph can be directed can be undirected it can be anything in in yeah you can take a pair class in java also you can create a pair class in java also that's i think pair class and java do okay cool so we have learned how to store now the traversal techniques that we'll learn because without this as i said for people who are wanting problem solving probably let the lecture get uploaded fast forward can you do anything for people who wanting to just watch your problem solving when the lecture gets uploaded fast forward and see that traversal techniques there are a couple of traversal techniques one is dfs which is depth first search the another one is bfs which is breadth first search again yes if nothing is said then it's the graphics can be the graph is an undirected graph if nothing is said the i have to i teach i teach faster because in cp when i teach in a batch when i teach they know basics over here people are like okay df is depth first search so we're going to first learn dfs this is done using requestion then you're going to learn bfs this is done using a queue okay so if you don't know recursion you will not be able to understand dfs let's understand dfs it's very very simple it's very very simple okay let's understand dfs let's see a graph is this a graph is this a graph is this a is this two graph or two component two component right so all the adjacency lists look like so we just draw the uh if i super quickly draw the adjacency list this will look like one two attached with six five is attached with one and three six is attached with four this is how the adjacency list will look like this is how the adjacency list will look like right this is how the adjacency list will look like i hope everyone understands basically adjacency list every index stores the nodes which are neighbors of it every index stores the node which are neighbors of it that's how adjacency list does work now how will dfs work now if i say like hypothetically if i start from 1 and then i go to 2 then i go to 3 then i go to 5 it's a depth first [Music] so explaining you in a better way if this is the graph got it understood clearly so the depth first search can be called as first one then two then three then four then five then six then you come back seven then you go eight that's the depth first search got it it can be opposite way like one two three four seven eight five six could have been this way too could have been this a way to again when i get deep go deep cool uh so everyone has gone very deep now so come back from that deepness seriously okay uh next so over here can you just do a single dfs and will it work no you you definitely need to do multiple divs because doing a single dfs will never work it's it's practically impossible because if you start from one if you go under you cannot go back right and there's no there's no convention there's no uh convention so what you will do is yes what you'll do is you will say hey listen what i will do is i'll create a visited array okay let's create a visitor array this is something which is known as visited array and in this you will be like 1 2 3 4 5 six and you'll mark every one as zero zero which means unvisited you mark everyone as unvisited now what you will do is yes now what you will do is you will start off yes you will start off with the main guy but in order to do that it's a very important technique which should be followed across across every day so what you will say is hey listen for i equal to 1 i lesser than one i plus plus if if visited of i is i'll be the 20 years now if i haven't yet touched i'll go to that and um initially i is one so visited of i is zero is it visited of one is it zero it is off so before going remember this if the dfs for someone is called marketers visited if the dfs or someone is called mark it as visited okay so you mark market as visited after that i teach like this only don't make a mess of it unnecessarily okay so dfs one right dfs one hello whenever you reach two now two will say who are my neighborhoods one or three will be equal i'll go to one sorry one cannot be gone one you cannot go back to one because one is already visited egypt whenever two looks for its neighbor one of the neighbors is one one of the neighbors is one you cannot go to that because so you will go to three you will go to three and the moment you go to three your market has visited he's taken so you'll go to five when you go to five one is so market is visited one is taken three is taken so five does not have notes first year twenty one two three five you went down downtown aquibachini so i'll come back back come back come back come back so the dfs is over do you observe something started from one two got it now remember now when you come will it go to five will it go to five the call for five will not happen the call for five will not happen got it is this clear is this clear congratulations sam okay got it i'll take some more examples don't worry i'll take some more examples now coming across coming across what i will do is i will increase this value to 2 2 is already visited i'll increase this value to 3 3 is already visited i'll increase this value to 4 ic 4 is unvisited 4 is unvisited so i'll go to dfs and i'll say hey dfs go to 4 hey dfs go to 4. so i'll go to four four will say my my my nearest guy is six so let's go but before that i go to six right i go to six six the six above is this is already visited don't go come back come back next goes to five already visited next gets to six already visited so can i say i did a perfect dfs traversal in both the components using this for loop i'll take one more example don't worry can i say did a perfect rdfs traversal by doing this can i say this one let's take one more example let's take one more example okay so this is a graph yeah this is a graph and let's assume this is connected to this this is a very big graph so let's tell me let's tell me if i start dfs the initial dfs call will start from one okay one will have this adjacent node like if i just write one will have the adjacent node as two and eight wave meters so make sure whenever you go your market has visited so yeah like i'll market visited here only either remarkable that they visited once adjacent who is one adjacent who's one's where will dfs go yes where will dfs go two and eight yeah twenty perfect so i can i can probably go to two the moment i go to 2 i'll mark it as visited visit it next from 2 where can it go from 2 from 2 it can go to 1 and it can go to three from two it can either go here or either it can go here but can it go back to one naive band already already okay so we will not go there instead of that i will go to three and i'll be choosing from three where can you go three can go to two but that's already visited three can go to four yes can go to eight so you can either go here or you can either go here let's go from 4 where can you go from 4 either to 3 but that's already visited either to five okay or either to seven so either five or either seven let's assume you go the other way seven let's assume just assumption from seven where can you go either to four either to six either to four or either to six correct six specialty right from six where can you go either to five or either to seven can you go to seven so you will go to five go back this sixth guy this sixth guy said i can only go to five rumors still this seven said i've already gone wahpusha this four said i've already gone to both both these guys so go back now comes the main point you have to understand 18 foreign so now we will try to go to eight did you understand sorry not here did you understand yaduri khani did you understand this leftover story because three went on this jacket again okay so we will go to eight now eight says where can i go eight can go to three that's visited eight can go to one that's visited so it will say either ten or nine picture so i'll just go to dfs of ten then we'll go to nine and then we'll backtrack backtrack backtrack and it's over did you see the dfs happening did you see the dfs happening did you see the dfs happening foreign right perfect perfect so let's write the code the code is very simple the code is very simple okay so i'll try to write the gold okay try to write the code yeah looks fine so let's write the code generally in general in competitive programming all competitive programmers are habituated like this i am also very happy to read it so i'll also do [Music] m yeah it's good it's good that you guys are nowadays appreciating good creators that's that is something which i always was supporting always appreciate it's very important that you appreciate the correct person who's working hard right for java code refer my channel you'll get all the java codes okay uh so how is it visit of i is equal to equal to 0 then you say dfs of i right that is what you do right that is what you will do so i can say void dfs as a void dfs ind node what can i say visit of node and i can say visit of node uh so after this work now how do travis traverse for all adjacent nodes foreign right so what can i do for auto of adjacent like this is the way you can iterate like if you just because adjacence of u do you remember adjacence of u is a vector if you run an auto for each loop that will automatically run on the adjacent nodes so if if if the adjacent node is unvisited then you will call bhaija understand to understand is this clear is the code clear every node you get you know till the dfs is not completed the next adjacent dfs will not be called got it got it yeah i'll explain i'll explain i'll explain don't worry i'll explain it okay got it right if you need the adjacent notes of one how will you get how will you get the adjacent notes of one tell me that now tell me that first isn't it adjacent of you isn't it adjacent of one isn't it adjacent to one what will add this into one store two and eight do you agree that isn't real stone now one cut two comma eighty two stroller one got to come into the store right right let's show all the all the notes right if you look at over here oh sorry sorry my my bad add this so adjacent of node means visited whatever you're storing whatever and vector of india you're storing on the index it will iterate it light rate on that portion got it again uh i cannot help if i go fast i will have 50 users okay so for people who won't fast i have already made a series now go and watch it it's fast it's very fast now clear is it clear now yeah if it is three notes if it is three notes assume if it is like this foreign okay so can you tell me what is uh what is the complexity can you tell me what is the complexity of this generally what is the complexity of this tell me what is the complexity of this let's analyze we're using a for loop we're using a for loop over here right that's a b of n already that's a b of n that's running amazing that's a b of n that's running for loop next for dfs if i'm doing a dfs big offend all nodes will be touched at least once now every node will be touched at least once right so by the way guys uh for everyone who's saying vector of vector in the yeah this is this is an array adjacency list it's an array of vectors it's an array of vectors it's correct it's correct or if you're using vector of vector it's a different way of defining you can try that out too okay so we go of n for touching everyone inside that you're running a loop for every adjacent notes for every adjacent notes how many adjacent notes in total do you have how many adjacent notes in total do you have isn't it we go off isn't it it is not n into 2m because overall the for loop how many times will that for loop run that is equivalent to the number of adjacent nodes and what is the number of adjacent nodes isn't it 2m so i can just generalize this to a big o of n complexity clear is it clear like i'll take the generalized version this this can be like might be might not be an if if it's a single component this is not required if it's a single component you don't need to write a for loop right you don't need to write an external follow with a single component got it is this clear explain tc again please yeah sure uh so basically we go of n for the for loop that we are running this for loop b of n for this now you're actually visiting every node you're visiting every node so another big of n that's a 2n n plus n now you're running you're going across you're going across every every node you're going across every adjacent node so in total the number of adjacent nodes are 2m because for every edge there are two nodes right so adjacent nodes are 2m in total you'll go across that these many edges will be there that's why so overall i can say we go off to n again okay clear 2m because overall notes for m 10 o'clock in the night it's 10 o'clock in the night is it clear yeah for single component you can call it as big of n plus 2m so don't complicate this keep it as n just keep it as n that's okay you can you can tell the interval it's a big off and it's it's they will not tell you anything foreign foreign it's not b2 off and it's big off it's very tough we are teaching 500 people live algorithms is very tough people teach but have you seen live 500 people like at least we had 800 when we started have you ever seen have you ever seen 800 live in a live class yeah for a week 10 p.m okay i'll give you five minutes break a lot of people asking five minutes break yeah you can ask your questions other silly go check something civil services preparation foreign okay let's get started so we learned about dfs okay it's a wonderful technique but where is it generally used where it is generally uh used we will come to that we will come to that but uh before that yes before that let's learn one more technique which is known as bfs it's very important most of the coding problems are solved using this technique actually most of the amazon or all these questions are solved using the technique that's known as breadth first search let's understand what is this breadth first search okay uh let's understand something very important now there's nothing like any hit let's not create controversies [Music] one next breath breath next breath but just remember one thing uh the guy who can write in a telegram group this stuff he wrote in the telegram group this this thing okay so i don't have respect for breadth let me give you one more graph if i give you one more graph so can you tell me the bfs for this can you tell me the bfs for this can you just quickly tell me what will be the bfs for this graph yaga is you just quickly tell me the bfs for this if there are two graphs then the breadth first search will be different for the first component and the second component okay utkash thank you thank you a wonderful question let another bfs for this everyone start with one start with one and tell me what will be the bfs no no bfs you start from here you travel in the equal equal depth foreign oh got it okay cool cool perfect this can be one three two also as long as you're visiting this can be one three two this can be five four hours it's okay it's okay it's okay as i said it's okay got this okay let's assume if there are two graphs and a graph like this then you can have any graph yes you can have any graph either the component one or the component two first no matter one then it will be just two then it might be five might be three you can write anyways that's your choice three five is also okay then then four and six together or six or four and then seven that's how you do it next eight next nine and ten together or ten and nine it can be any any any option got this it can be any option here say bfs is the is the example clear basically eight direction right next to direction next this this this so this and this next this a kick step one one step that you're taking one one step that you're taking bfs got it yeah an academy has dvd has stopped the cp subscription they will probably start with something else cool uh so how do you do this it's very simple let's take a very very simple uh common example let's take a very very common example so if you take this what you will do is very simple you will take a queue data structure remember this you will take a q data structure a very simple queue data structure is what you will take and what you will do is if this is the node again use the visited concept let's create a visited concept so let's create a visited concept okay so if this is one yes if this is one what you will do is you will mark this as visited and you'll put it into the queue all right next who is the adjacent node so this this is what you will start a queue data structure with the root a queue data structure with the root of the tree sorry root of the graph just a minute one message catcher a queue data structure with the node initial node and make sure you mark that as visited you'll make sure that you'll mark that as visited next let's move across and take this out take this out this is your node now of this node who are the adjacents of this node who are the adjacent only two what you'll do is insert that into the queue and mark it as visited perfect for one all the adjusted notes are done next get the next element out of the queue two next get the next element out of the queue that's two who are the adjacent of two three take it and put it into the queue and mark it as visited take it and put it into the queue and mark it as visited done what is the next you're done with two take out three who are the additions of three for three the adjacent is two four five but but but three is already visited for three two is already visited and 4 is left 5 is left so take 4 take 5 and put it into the queue take 4 take 5 put it into the queue in the next thing in the next thing take the next element out which is four again do the same thing for four who are the who are the adjacent nodes for four who are the adjacent nodes or four we see that the adjacent node is three which is already visited and six so you'll just take six and put it into the data structure perfect done next you'll get five now you have a five right you have a five so what you see is five is there for five what the adjacent notes six or five six is as adjacent notes and three is one of the others what you'll do is you will just simply take yes you will just simply take something else six that's already put i guess that's already put visit here let's get the next one that's six six is done who is the adjacent of six five visited four visited take seven put it and let's take seven so if you look at the look at the bfs first one then two then three then four then five then six then seven did you understand how to do this did you understand how to do this you can start from anyone see it's not necessary you need to start from one it's a convention it's a convention that you generally start from one it's not a stand rule it's not a stand rule that you have to start from one that's the difference it's not a convention it's just a star rule got it cut it shall i code this you can start from anyone it's not it's not a standalone it's just a convention that you start from one generally we start from one if there is no mention generally we start from one if there is no mention shall we code the bfs so we can again write the for loop for component wireless stuff remember the component so i'm not writing the inputs the inputs will be same the inputs will be same the inputs will be same just in case of dfs it will be a bfs just in case of dfs it will be a bfs bfs of note okay so you'll write visited of node equal to one you can probably create a queue and you can say q dot push off node and next what you can do is while dot q empty and you can say int the node will be q dot front you just get the front element and again the q dot pop and then you can just traverse for the adjacent notes of these guys and if it's not visited of it you can secure like visit of i t is one and you get the q dot push of i t and then you like over here you can just uh a way you can just do this is that clear is that clear is it clear i have taken a recursion class you can check that out a lot of other instructors taking you and check it out done everyone has understood the code clear yes yes if there are two see that's why i've written you over here right if there are two components it's gonna be doing a bfs if there are two components there is going to be a bfs right let's understand what is happening you're calling bfs right so initially you go and say okay let's mark it as visited so let's mark it as visited next you're saying hey q you started from here so let's let's take this into the queue i'm like okay next take that node out yes i'm taking that node out and that's a part of my bfs so that is what i've done whatever are the adjacent notes whatever are the adjacent notes i just take it off yes i just take it off and i mark it as visited and i push it into the queue got it for every node node adjacent adjacent adjacent take it put take it put take it put got this so the next time when it comes up it will again get that guy and his adjacent you'll take and put take and put got it is that clear is it clear yes quick yes can you just write a quick yes a complex device what's the complexity can you analyze me the time complexity or complexity time complexity so the time complexity is specifically b go off n plus again a big o of n plus big of 2 m it's a similar time complexity the reason is same it's a similar time complexity it's a similar time complexity this for components uh this for traversal and this for the adjacent nodes similar time complexity right right similar time complexity perfect perfect perfect so so you've learned couple of techniques one is the bfs and one is the dfs right they've learned that perfectly now what will we learn yes what will we learn learn the next thing that's very important solve let's solve a problem using bfs let's solve a problem using bfs and let's see let's see if you if you can give me some answer again uh generally rudra it's written v plus and they do not consider the component of a loop because they always consider a graph as a one component so i am taking the extreme worst case where the graph might have multiple components again got it clear test is similar to similar to that guy test case similar to the yeah okay let's solve a problem both of them are same both of them are same both of them are same there's no need to do anything different that both of them are same dfs bfs you can use any one okay so remember one thing uh big of n for for loop big of n for every node every node every node and big of 2n for the inside for loop that you're running okay for topics you can watch my playlist you'll get all the topics okay just got time mister you can watch my playlist there is all the topics there okay using a bfs let's understand the question i will give a start point okay i'll give you a start point and i'll give you end point so basically i'm giving you a start point as well as an end point okay the end is 30 that i'm giving to you then is 30 that i'm giving to you now i'm giving you some uh like 2 comma 5 comma 10 i'm giving you 2 comma five comma ten an array now you really like graph product over here there is a logic of graph that you will see you'll see how graph is implemented in this problem okay so 2 5 10. now i'm saying i have a start i'm saying i have an n and i have an array of 2 5 10 so what i am saying is listen i want you to tell me what's the minimum number of operations minimum number of operations required i want you to tell me what's the minimum number of operations required now what do you mean by a minimum number of operations what do you mean by minimum number of operations i say if you do 3 into two into five from start you will reach end from start you will reach end if you do three into ten you will reach 30 which is again the end so over here you required two multiplications over here you required one multiplication okay what if what if i change this end yes i just change this end and i probably say this is 12 i probably say this is 12 in that case it will be 3 into 2 into 2 so there will be again something like this so you can use a number as many times as you want an array is given you can use a number as many times as you want okay and you just need to multiply you just need to multiply if you can reach from start to end you will print the minimum number of operations if it's practically not possible you will print minus 1 if it's practically not possible you will print minus 1 is that clear is it clear what's minimum the minimum number of multiplications you need to do minimum operations is the minimum number of multiplications you have to do utkash minimum number of multiplications that you need to do yeah that is okay but how will you find the minimum number of operations in short you have a start you have an end you can multiply array indexes any array element you can keep multiplying array any index i j any index and then you need to reach end the number of times you multiply those are operations and you need to minimize these operations you need to minimize these operations you need to minimize these operations nothing else you need to minimize these operations so [Music] thank you so much it's amazing how do you do okay first i'll multiply the largest number obviously greedy will not work obviously greedy will not work because let's assume uh the array is 2 5 10 let's assume that is uh 2 5 10 and we are like uh we are having the starting point as somewhere around let's say 2 and the ending point let me just think 200 no okay uh 100 except the ending point is 100 again so let's visualize this as graph let's visualize this as graph i will say let's consider this is the root of the let's consider this as a root okay let's consider this as the root of the graph let's consider this as the root of the graph let's consider this as the root of the graph okay now what i'll say is what options can you do with this if you like i can multiply two i can multiply five i can multiply ten i'll be like to say and this is the second level of bfs okay next let's do the next thing let's do the next thing again four p will be like hey into two hey into five hey into ten i be like eight twenty this is the same thing again 2 20 5 50 10 100. oh we reached 100 we reached 100 answer as much i'll tell you i'll tell you why not recursion i'll tell you why not recursion don't worry i'll tell you why not a question why not recursion i mean if you understood this get me a thumbs up first then then i'll tell you why not recursion i'll tell you why not recursion but palette is something why why bfs why not recursion why bfs i'll tell you if in bfs we don't have to go into depth always take step take why bfs understood why not dfs and why bfs got this well let's uh let's solve this using the bfsc easiest way like you you can use dp that's okay but that will still be a lot of time you can use recursion plus memoize but since we are learning since we are learning something as bfs i wanted to tell you how will this be implicated they're learning something as bfs that's why i want to tell you okay now tell me one thing tell me one thing can i use a visited guy can i use a visited guy and they visited why that's again very important why let's understand why is important here like why do we need to visit it in order to prevent multiple there are two twenties there are two twenties will it make sense to like for example here is also twenty so when you multiply 2 like assume 100 was not the answer assume 40 when you multiply 5 it's 100 and when you multiply 10 it's at 200 so you have already got 40 you have already got 100 you would have already got 200 so will it make sense to again do the same kind of multiplications because if you do one more time the number of steps will be zada will be zada that's why we use a visited got it got it you just need to do it once just need to do it once because if once 20 has been multiplied with all the it's important that the user visited if that path has already been traversed there is absolutely no need to do again got it have you got this have you got this point why am i saying why am i saying maintain something like a 20k visited yeah you can call it as something like memoization technique like not memorization it's a hashing it's a hashing it's a hashing so can you tell me when will you stop multiplying can you tell me when will you stop multiplying it tell me when will you stop multiplying internally when will you stop multiplying raj i am pankaj foreign okay let's let's solve it let's solve it again so yeah the moment you cross end you don't need to write it so let's solve it assuming of the start assume you have the end assume you have the array assume you have the start assume you have the end assume you of the array so what's the first thing that you will do you will definitely create a visited guy of the size of n plus one that's very important and you'll say visited of start is equal to one and what you can do is you can just probably keep a queue this time keep a pair of queue where a pair of queue you need to count the steps as as well right so initially uh you can definitely keep a start comma one you can definitely keep start comma one where you say start is the starting point and the number of steps taken is one correct so if just sorry the number of steps taken is zero and we can i trade in the queue and we will be like q dot empty and you can be like int node is q dot front dot first int steps is equal to q dot front or dot second and uh you can after that do a q next you can just go on to auto of i links sorry not auto fighting to all the notes in in in the array which you need to multiply and you can say best destination will be the node value into array of i if the destination is lesser than equal to end and and is not visited very important and and is not visited right and and is not visited what you will do is you will say okay it is not visited so i will take the destination and the steps will increase by one and the steps will increase by one okay and then keep on doing this every time please make sure your market has visited also and any moment yes at any moment you reach a node which is equal to end you can say these are the steps which are required and if you keep on multiplying and you run out of multiplications you can re return minus one and you can return minus one okay it's not it's not memoration it's kind of a hashing that you're doing yeah initially you start with start so you mark it with one and you say the number of steps taken is zero so we start with start the number of steps taken is zero so we just put it next that the queue is not empty if the queue is non-empty then we start the node and steps is what we take the node and steps is what we take and we have taken the node and steps so over here we have multiply multiply multiply this is what is being done here multiply multiply multiply and if if the destination is before end just and see if that's not previously visited put it into the queue and mark it and any moment you get the end you return steps and you're gonna return minus one right it's not a lead code problem clear okay it's a good problem it did come up in one of the coding rounds it did come up in one of the coding rounds that is why i did i do remember right now that's the problem problem anyways can you just quickly tell me will be the time complexity before just wrapping it up let me just quickly tell you with the time complexity before wrapping this up art will be the over the time complexity if you uh okay stories be it whatever you are doing if you are sharing this please make sure you tag me together okay cool what's really the time complexity very simple can i say you will visit all the notes at the worst case you will visit all the notes from the start till the end can i say the complexity will be end minus start plus one like in general atomic yes or no yes or no it's already droop while inserting i'm already marking it as visited will the complexity be this n minus start plus one n minus start plus one yes because at worst case the number of nodes it will visit will be saare elements unke beach correct i'll change the tab forgot now group uh while inserting if you do it it's okay while inserting it the insertion getting visit marks okay so basically end minus start and minus start that's correct absolutely correct i don't think my english is that good they have achieved everything in their life right uh right next what did i do i did a multiply two i did a multiply five i did a multiply thing so eight comma two twenty this twenty will no more be taken why because this twenty was taken correct and this way you can just go on okay uh thank you guys for joining in uh it was wonderful it was wonderful like absolutely i was absolutely glad that you guys joined just make sure you do this uh if if you're sharing it anywhere tag me uh be it linkedin beat anyway uh instagram anywhere if you're sharing it please tag me thank you thank you guys you can follow me everywhere at uh this user handle which is trevor underscore seven nine uh i go by the name raju kramati at linkedin you can definitely follow me there cool guys uh bye bye take care but the time complexity will be yeah into n into n sorry notes into and one visits into n number of number of n minus start plus 1 into n into n yeah cool guys

Channel: CodeBeyond

Views: 15,536

Rating: 4.9522614 out of 5

Keywords: competitive programming, striver competitive programming, solving interview round questions, interview questions by raj striver, leetcode practice, leetcode questions solutions, leetcode contest, leetcode solutions, live problem solving, faang, faang interview questions, leetcode biweekly contest, graphs by striver, concept decoding and problem solving, graphs master class, decoding and coding, coding and decoding problems, raj striver, graph, coding, decoding

Id: 1v-xWsqWjeA

Length: 130min 8sec (7808 seconds)

Published: Sun Oct 03 2021