6.2 BFS and DFS Graph Traversals| Breadth First Search and Depth First Search | Data structures

hi guys in this video I'm going to discuss with you graph traversal techniques two types of graph traversal techniques are there BFS and BFS BFS means breadth-first search or sometimes it is also known as level order traversal and the DFS s depth-first search fine so we'll take this example and with the help of this example I am going to discuss with you the BFS traversal fine in BFS traversal when you will start then you can take any node as a root node you can start traversing this graph from any node suppose we can take a zero you can take one you can take six as a root node and you can start your driver self fine but sometimes intuition if it is given that BFS Traverse will find out can I have this graph and considering two as a root node then what you have to do is you're supposed to start from this two to approve not consider curve and you will start traversing this graph from this node only generally suppose in this example nothing is given then we will consider zero as a root node I am just considering zero as a root node you can consider one Phi for any node okay so for BFS traversal what a data structure is used that is q queue data structure would be used fine and here you'll write will print the result and this is our data structure that is Q I hope everybody knows you work in what fashion that is FIFO first-in first-out okay so in this traversal suppose we have taken 0 as a root node okay all the adjacent vertices of this 0 will be traversed first multiply to traverse all the vertices as close as possible to the root vertex C is K close the eye scared this into put no vertices give me here 1 and 3 to 0 is it or how about 1 or 3 or either 3 or one in any fashion a visit only after that you would move forward SN you're working zero key about one visit can you yeah then you would visit five okay first of all it may be what ourselves only as close as possible to this zero those who are what it says would be visited fine okay now see suppose we have taken zero as a root node so 0 would be inserted in this queue fine okay now in the result we have suppose we have deleted in this 0 and we have printed this zero in the result fine now as soon as the zero is printed means zero has been visited right now next thing what you have to do is zero purchasing has a delete over okay it may be adjacent what this assume is you're okay that would be inserted in this queue now adjacent what this is over the zero is 1 and 3 fine and one entry would be inserted in this cube 1 or 3 it's not like if one would be inserted and after that 3 you can insert three or one in any order you can insert fine ok now one and three ok now next is next element in queue is one now one would be deleted and what one would be printed means one go how many delete kill the edit one has all has already been visited the say print format loved one has already been visited now next thing what you have to do is one get it maybe at the same to what this is all the dis in tortoises of one adjacent vertices plus unvisited vertices fine adjacent unvisited vertices of one wouldn't be inserted in this queue see how many i descend vertices of one are there 0 3 2 5 and 6 the medic death you 0 3 2 5 and 6 but up go insert is makan say can hear only the visited what this's zero has already been visited fine zero has already been in visitor to zero copies mini insert karoge and three three has already been inserted fine the yeah be a boys main certain he Colonel Khan say is main certain gate to five and six to five and six you can insert two five six in any order that is you can insert five two and six you can insert two six five you can insert six five and two it is not compulsory that you'll insert two five and six only okay now next is three fine three you go hominid I said delete here and three would be printed and what are the adjacent vertices of this three find out those see this go home find out Korea all the adjacent vertices of any node score both exploration of that node you are going to explore that node fine now find out that at this into vertices of this three adjacent to vertices of this three rc3 company print Korea means that has already been printed or you can say that it already been raised it ready a fine home we have now three three cages into what s is gone constant upkeep as c0 hey you have one you have four you have two for adjacent vertices are there but inside a pecan say carne here to visit and I knew a sc0 has already been visited one has already been visited and two is already there in this queue though you would not insert to again repeat Nanaia for the only element left is that is for now for will be inserted in this queue fine now check next element that is to to be deleted and two would be printed means 2 has already been visited now find out at the st. element of this two adjacent element of this to r1 this 3 this 4 and this 5 for element we have one is already visited three is already visited four is already there in this queue only left is five no sorry five is already there in this queue so there is nothing to insert in this queue okay now move to the next part next element that is five five first is deleted from this queue and five would be printed means five husband visited now find out adjacent vertices of five one we have what we have - but these are already visited don't know what this is there to be inserted in this queue okay now check the next six six would be deleted and printed fine 6 min already visited at the same vertices of six are one we are not supposed to insert this one because this is already visited and one is four but four is also there through here we have this means hurt and he care of it next up coca political my four and four would be printed fine so this is the BFS traversal of this graph see I'm this is not the only BFS traversal of this graph there are numerous valid BFS traversals on this graph how see suppose you have inserted in this two five six in this fashion five six and two two zero one three ki baat karta happy - octopus take care so it depends how you are going to insert these numbers into this queue so I'm not saying so this is the only welded DFS traversal you can find out numerous value DFS traversal of this graph using this method fine now we will discuss the DFS traversal of this graph now we would find out the DFS traversal of this graph DFS means depth first search traversal of this graph okay in BFS queue data structure is used and as in DFS what data structure will be used that is stuck and it works only for minute last in first out okay so we'll have one stack fine and here we'll write down the result of this trevor self-same in that BFS we have taken any node as root node so in DFS also you can take any node as root node and you can start traversing from that node okay in case if it is given that consider one as a root node in that case of 100 root node Elaina he pareja but then he give and HECO you can take any notice root node suppose we are taking zero as root node okay now see zero would be inserted in this stack fine and zero would be printed okay now check how many addition what this is of zero are there 1 and 3 so BFS may have any idea how all the adjacent vertices of that node Dominic you say delete here just go print yeah okay sorry adjacent what this is commonly katha we have inserted into Q but DFS make a alga only one any one of that node would be inserted into stack depth-first search belly hump depth measure Angus suppose zero common a key after that we have chosen this three fine then we would go three two next is scared the sentiment it may be only for hoga suppose six who or something like that at some points we read suppose we have reached at six fine and SK our gate suppose I'm panicking a couch near this this 1 to 6 is not there let us consider those 6 k bar the panini's are set they after that you'll backtrack you will go to 4 busca path for K at this end image of the in case our pockets new multitudinous then you will backtrack fine but depth-first search MATLAB you'll go deeper and deeper until a dead end dead end min soos car a descent unvisited adjacent which many over and you have to backtrack fine so any one of this vertex 0 has 0 is printed to anyone of this zero would be taken anyone adjacent vertices of the zero will be taken and pushed into this stack suppose we have one we have one and three two adjacent vertices of zero we have so you can take either one or you can take three suppose we are taking one one would be printed and one would be pushed into the stack 0k by thumb camp again here this one after that you would explore this one explore any explore means you explore now they kept sorry what this is co-op Explorer ovo Explorer from Calcutta BFS maker thing now one car you would take any vertex unvisited vertex get my adjacent vertex 1 K addition vertex given vertex con-con same they pass 3 to 6 and 5 fine so you can take any one of these four BFS viiia Charaka insert name karna you take any one of these four three to five or six suppose we have taken this three fine three we have taken or three pop knee cap insert cardia high in the pushkar their head stack may up let's go push Korea fine so you are now it at this three now find out adjacent vertices of this three this for this to this one and zero but obviously zero and one are already visited fine zero and one see hero's ultimate equal zero and one already visited so unrelated vertex up go find out Carnahan and visited vertex Kahn same they pass to and this for so you would take any one of this were the these are descent with the unbusy two vertices and you would push that vertex into this stack up to village therefore be less active suppose you have taken two to go up in a print here to go up in a push kardia into this stack three Chabad aapke hey ho do fine now you are at this - now find out at the st. vitus's of this - fine you scared this invert this is gone same one but you cannot push one at this one because one is already visited you cannot push three three is already visited now but you have give us a decent what this is five five cop is no push cars are still fine and one is this for adjacent vertex fine this five and four so you can take either five for either for anyone take a pulsar in a hill a name a bar wise we focus car do any one up quark tools come and that is unvisited vertex or scared this end bit notchy so you can take either four or five suppose we have taken four for common a push cardia and for co-op nikka hop a spec print bigger than take a talk about topic I am for now find out adjacent vertices of this for fine three here but three is already visited two two is already visited and one is six yeah you can push 6 because 6 is 2 and visited the for Capcom bad kappa going up six three six print table and six would be pushed in this stay now find out after six is there any unvisited adjacent to vertices of six he scared this and what this is for but for is already visited adjacent verses of 6 1 is 1 1 is already visited and we have only 1 and 4 so no unvisited adjacent vertices is there fine yeah happy cuyahoga now you cannot move you know further from the six deep me up 6k 1 these are certificates you do not have any unvisited at the central doses of six charges of to do you have a yoga backtracking a backtracking case yoga backtracking me Jonica except attach alegre from this step again I see situation at the Ava hop a key out here one can one that stop is there the topmost element is deleted popped out or you can say popped out then six would be pumped out six poo powder Shugar fine now say the next top element is for a visa package elegantly from six you would go to which element this four element then backtrack to four fine I am now check this for has any unvisited at the center what takes still HECO is força three to six all are visited nor Texas there then four would be popped out from the Staten F next element is two now we would go to to backtrack to to now find out is there any adjacent vertices of two that is still unvisited yes we have what is that this fine this 5 is still invested and it is adjacent of this too though you would go to this five five would be printed and five would be pushed into the step fine now check five is there any adjacent vertices of five which is still undecided no one already visited two already visited what the next step is we cannot go further from five top of backtrack on a backtrack aha corner first step is five would be popped out from the stack ticket the top element would be popped out now check the next top element that is two then five say backtrack can't be hanging to the two now a is there any animated vortex of two that is adjacent of two and still unvisited no one is there okay then pop out this two now next s 3 so to say backtrack AHA pay only three now check out is there any animated vertex adjacent vertex of three zero two four one all are visited then pop out this three from the stack and next is next top of the steak is one so from three we would go to one Joby's kostik Kotoko gram happy I'm dying it see is there any animals it adjacent what this is a one that is you can push into the stack no all vertices are visited you scared the center though pop out this one from the stack and find out the top that is zero now from one way would go to zero find out zero Kaku here descent water says that is still done visited no then pop out the zero from the step now see stack is empty so this is the indication where you have to stop this BFS algorithm fine and this is the DFS traversal of our graph now in this case also this is the only you know this is not the only DFS traversal there are numerous value to DFS traversal of this graph how you can find out C suppose you are starting from zero Hermia has a zero say start Karangahape le to one but from zero you can go to this vertex 3 also take a whiskey by the visit karoge so this would be another DFS traversal fine so I say brought sorry is my DFS traversal okay Oh such a the BFS many up go but are they a BFS make alga all try to explore all the nodes as close as possible to the root node means level order is scared yes and it may be homie paleo sorry explored me after that you will go further fine but DFS make alga any one node would be visited from that root node loose Chabad whose notes a further up visit kirovsk about further further and further you will go deeper and when you will reach that dead end Jos a aapko you know you don't have any unbudgeted adjacent vertices then you would backtrack or backtrack a poke a sabotage it occur from this stuck they say I'm dead end pay poncho V that top of the stack would be popped out fine next dope I got perhaps emo happen school backtrack appear google fine so this is the DFS traversal DFS one another difference is the DFS may up coke out the stack data structure user go DFS sorry BFS macaca kyu-ho call TFS Makabe Stanley the structure won't be used ok then bye see you in the next video

Channel: Jenny's Lectures CS IT

Views: 1,323,503

Keywords: bfs, algorithms, graph, dynamic programming, data structure, abstract class, dfs, sorting algorithms, algorithm analysis, algorithm examples, graph theory, Breadth First Search, Depth First Search, dfs algorithm, jayanti khatri lamba, jenny lamba, ugc net computer science study material, GATE computer science preparation, engineering, it, cse, android, c programming, jenny's lectures, bfs and dfs, NTA ugc net syllabus, data structures and algorithms, programming languages

Id: vf-cxgUXcMk

Length: 20min 26sec (1226 seconds)

Published: Thu Jan 24 2019