5.1 Graph Traversals - BFS & DFS -Breadth First Search and Depth First Search

hi the topic is dreadful search and depth-first search in this video I will cover these two traversal methods by taking various examples well for such an effort search our graph traversal methods so we'll understand quickly the difference between them throw this a small example then afterward I'll take another example and I will explain you in detail now for quick understanding I have taken a simple graph actually it's a tree but a tree is also a graph so let us see so for traversal both of these traversal we have to know these two terms now for understanding these traversals we should know two terms one is visiting a vertex means going on a particular vertex second Irma's exploration of vertex exploration means if I am on sub particular vertex then visiting all its adjacent vertices is called as exploration so based on these two terms we can understand traversals so first I will explain in breadth first search see I am selecting vertex one as the starting vertex to find out breadth-first search we can select any vertex as a starting vertex now vertex one I will visit the vertex one now once the vertex is visited this word is I will start exploring means I will visit all adjacent vertices so who are those five four and two in which order I can visit I can visit them in any order so okay I will take two first then four then five next I should select the next vertex for exploration so these are already visited vertices after one I have a set at two four five then I should explore explore what I will explode - so who are a listen to two adjacent to two or seven six three in which order you can take you can take them in any order 7 then three then six in any order you can take that's all all the verses are visited and there is no vertex remaining for exploration this is breadth-first search now let us look at depth first I'll start from vertex one then from one I have stowed start its exploration so I will go to vertex two - now who are other adjacent vertices four and five no don't visit them you have reached a new vertex so you start exploring that vertex okay I'll start excluding - then who are adjacent to this seven six and three so I want to go to three okay go to three then shall I use it six and seven also known this is that first search start exploring three so if I start exploring three there is nothing connected to three okay so it means three is a completely explored then come back and then continue the exploration of - so who are there six explore six nothing is there come back go to seven explore seven visit seven explore 7 there is nothing so come back to one now and continue the exploration of one who are adjacent to it for visit fool and explore for there is nothing come back then go to five five no in this way all are explored so the Traverse cells are different results are different so in breadth first search we will explore a vertex then we go to the next vertex for exploration but in depth first search once we extracted exploring once you visited a new vertex we will suspend this vertex and start its exploration so from one we got two so we started exploring - then from - we went on three so we'll start exploring three like this so when the first search approach is different and breadth for such a process is different so I'll take one more example and explain you what is the difference between that first search and depth-first search with a simple example one more example let us find breadth-first search actually this is a binary tree tree is also a graph so let us perform for search and see so as per binary tree I will perform level order 1 then 2 3 then 4 5 6 7 4 5 6 7 this is breadth-first search means breakfast surges just like a level order on a binary tree then what is the depth-first search visit one ok Explorer 1 so he got two so stop exploring one and start exploring two so four stop exploring two and continuing exploration of four there is nothing so go back and come to five now nothing is remaining so go back to one and come on this side then six and then go back and seven so this is like pre-order so that first search is just like level order and depth-first search is just like pre-order traversal of a graph I have taken a bigger graph now we will learn about bid for search and the first search in detail first of all breadth-first search for performing grid first search I will take one data structure that is Q I have taken a cue now I'll explain you initial step then I will explain you repeating step so what is the initial step start exploration from any one of the vertex so which what x I should select as a starting vertex for that for search you can select any what else you like so I will select vertex one so in the answer you show it one in the graph you draw here again then add it to Q this is the first step initial step now we will perform repeating steps so what are those repeating steps take all the vertex from Q and start exploring it so what X 1 who are adjacent to 1 4 & 2 so explore them so first I want to visit for okay add it to result and also add it to Q next to go to to okay added to result and also added to queue no one is completely explored there is no urges on vertex remaining for vertex one this is first iteration completed now repeat the procedure what to do next select next vertex for exploration from queue that is for start exploring for so whose at this into four three so I am drawing it like a tree here so three is adjacent so add it to queue any other adjacent for for nothing is adjacent for four so four is completely explored now select next vertex for exploration that is two who are adjacent to two three five seven eight I can visit them in any order if I check three it's already explored so then I will prefer going on five first so five five next I want to go on eight okay eight so eight and eight next I will go on seven so seven and at seven here not two is a completely explored now select next vertex for exploration who is that three is there any at this one over this is for three yes to eight nine and ten so two is already visited so first I will take ten ten ten and then nine nine added to queue completed three is completely explored now select next vertex for exploration five anybody had just sent to five yes eight and seven and six so eight or the D visited seven already visited 6 this is 6 so 6 and 6 5 is completely explored select the next vertex for exploration 8 who is adjacent to 8 2 and 7 - actually we came from there 7 lloyd dotted line so vertex which is already visited we are drawing a dotted line then next vertex for exploration 7 7 is already explored so is there anything remaining four seven No ten there is nothing nearer to ten no nothing I just said to ten there is nothing as at the same to nine and there is nothing at the same to 6 so that's all this is breadth-first search completed and the tea that we got here is breadth-first search spanning tree dotted edges that we got here they are called as cross edges they are called as cross edges let us see what are the things that we have learned first thing as you can start breadth first search from any vertex you like first point second thing is when you are exploring any vertex 1 then you can visit the suggestion vertices in any order you like this or the second thing then both are leniency is given freedom is given to select any vertex then what is the rule here rule is when you are selecting a vertex for exploration you must visit all its adjacent vertices then only you should go to next vertex for exploration so it if I am exploring one then I should explicit a for as well as two then only I should sell it for for exploration this is the rule the next thing is last thing is you should select our next vertex for exploration from Q only so Q and exploration should be completely done these are the two important points about that first search you follow this one then you can get many answers I will write few more valid breadth first search is here first one I'll start from vertex one that is explore the adjacent vertices so first I'll explode two then four then I have to start exploring two because I have added to first so who are at this into two so I will take eight then five and seven then these are Addison to to all these are a different - - then I should explore which one for so water just sent two for three solid over then explore eight who is adjacent to eight five and seven both are visited now explore 7 so this is six now explore three so ten and nine so ten and nine this is one also this one is also a valid answer then one more I'll start exploration from five from five who are adjacent to eight seven and six now explore two who are resistant 2 to 3 and 1 now explore 8 7 is already visited 7 everything is visited 6 and nothing is there so everything is visited explore 3 so 9 + 10 + 4 so 4 3 9 10 and 4 I have visited 9 explore one nothing is remaining nine ten for not all are visited so this is also valid so like this you can start from any vertex and you can visit the adjacent in any order so you can form numerous number of valid breadth-first search next we will see depth-first search now next is depth-first search for this I will take a stack stack as a data structure used here let us start I can start the traversal from any vertex highlight so I want to start from vertex one so one is visited this is the initial step now the repeating step what I have to do every time as this new vertex is visited start exploring it so or adjacent to that four and two so visit four four four now the role in the first searches once you have visited one vertex still one more is remaining leave that we will see it afterwards first you start exploring four so this is the rule so once you have reached a new vertex start exploring that new vortex what about that one suspend it and keep it in the stable we can explore it later now start exploring for so from four I can go on three so they go to three three is visited now what to do suspend for and start exploring three from three I can go on ten so ten suspend trees start exploring ten there is no adjacent vertex of ten so go back to three so how to know I wait I have to go back this stack will give me their value so this three continue exploring three so I can go on nine 9 and again suspend tree and start exploring 9 from nyla cannot go anywhere then go back to 3 and start exploring 3 so who is the descent to 3 2 so 2 is visited then from 2 whose adjacent suspended to and start exploring two so from 2 8 is Addison so take 8 now start exploring 8 so from there I can go on 7 so suspend 8 so 7 is visited now we have to explore 7 from 7 I can go on 5 so 5 is newly visited now we have to start exploring Phi so suspend seven and push it into the stack then from 5 who is adjacent 6 so visit six suspend 5 and continued exploration of 6 there is nothing at the same to 6 so go back to 5 from 5 where I can go further so I can visit 2 which is already completed right I can visit 8 which is already completed so there is nothing remaining 4 5 so what happens in this way is we are going deep and deep right so in this way almost all vertices are visited only they are completely explored so 5 is completely explored go back to the previous vertex who is that 7 7 from 7 very can go from 7 they can one two which is already visited then go back to eight from eight nothing is remaining so from to where I can go I can go to one right then nothing is remaining so go back before from four I cannot go anywhere from three one I cannot use it anywhere so that's all right so here is the defer search traversal result and this is a DFS spanning tree this is depth full search spanning tree and these are just are called as back edges so for this graph we can make a tree like and perform preorder so this is the pre-order of DISA tree c14 310 then nine then two eight seven five six one four three nine eight two so nine two eight seven five six so this is like pre-order traversal no I will write few more valid depth-first search directly looking into the graph I'll start from vertex 1 1 this is the first one from 1 I will go to tea from - I'll go to 8 from 8 I will go to 7th from 7 and go to 5 then 6 from 6 I cannot go anywhere come back to 5 2 is already completed 7 also completed so what was the route I have taken so come back to 7 7 is completely explore come back to 8 nothing remaining come back to 2 so from - I'll go 2 3 then 9 nothing is there come back and go to 10 then go back to 3 and go to 4 then one is already explode so return back before then 3 then 2 then 1 finished so this is one answer then one more I'll show I'll start vortex train first is three then I'll use it to fool than 1 then 2 then 5 then 6 from 6 and 8 cannot go anywhere come back to 5 come back to 5 and go to 7 then 8 right from 8 and I'm back on to what is already over so simply go back to seven then five then come back to 2 then 2 from there I have already gone to 1 1 is already completed right so come back to 4 then come back to 3 so from 3 who are remaining 10 and 9 so 10 then 9 this is also valid so you can start from any vertex you like and you can visit any neighboring vertex but only thing is once you have visited a new vertex suspend the exploration of current vertex and start exploring new vortex that's all about the first search and breadth-first search and the time complexity of both these methods is order of n and this number of vertices

Channel: Abdul Bari

Views: 1,684,727

Rating: 4.9194722 out of 5

Keywords: algorithms, algorithm, breadth first search, depth first search, bfs, dfs, graph traversals, abdul bari, bari, gate

Id: pcKY4hjDrxk

Length: 18min 30sec (1110 seconds)

Published: Sat Feb 24 2018