{"id":405541,"date":"2024-06-29T18:23:12","date_gmt":"2024-06-29T18:23:12","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=405541"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=405541","title":{"rendered":"<span>Breadth\/Depth First Search<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>A graph is a kind of data structure that includes a set of vertices and edges. Graph traversing means a visit to each vertex of the graph precisely. The graph traversing is used to determine the order in which vertices are being visited throughout the search process. A graph traversing searches for the edges that will be used in the search operation without establishing loops. This means that using graph traversal, we will go to all the vertices of the graph without going into a looping path.<\/p>\n<p>There are two kinds of graph traversal methods.<\/p>\n<ul>\n<li>\n<p>Breadth-First Search<\/p>\n<\/li>\n<li>\n<p>Depth First Search<\/p>\n<\/li>\n<\/ul>\n<p><strong>Breadth-First Search (BFS)<\/strong><\/p>\n<p>Breadth-first search is also called a level order traversal. Breadth-first search is an algorithm to traverse the graph level by level. In the traversing process, we have to visit all vertices and edges. In this, we can take any node as a root node during traversal starting. For BFS, a queue data structure would be used that follows FIFO(First In First Out) principle. We visit nodes level wise. First, we complete the top level and then move on to lower levels.<\/p>\n<p>In breadth-first search, we identify the levels in the graph and then we visit or traverse all the vertices. Breadth-first search is level by level exploration of the graph.<\/p>\n<p><strong>Implementation of Breadth-First Search<\/strong><\/p>\n<p>The implementation of breadth-first search involves the following steps:<\/p>\n<ul>\n<li>\n<p>We take input as a graph to traverse it.<\/p>\n<\/li>\n<li>\n<p>For all edges incident on that vertex, we are going to check to see whether it is undiscovered or not. If it is an undiscovered edge, we check the vertex follows the undiscovered edge. If that vertex is visited, we mark the edge as a cross edge. If that vertex is not visited then we mark the edge as a discovered edge. We visit that vertex and add that vertex to the next level. Once none of the vertex incidents on the vertex is undiscovered, we start to explore the next vertex.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Example<\/strong><\/p>\n<p>Let us consider a graph shown below to traverse. At the beginning of the breadth-first search, all the vertices are going to be unvisited and all the edges are going to be undiscovered. So, we will symbolize the unvisited vertex by ( O ) and the undiscovered edge by ( \/ ).<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/6e3\/d82\/4a2\/6e3d824a237426ac365ef3643270026e.jpeg\" width=\"316\" height=\"220\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6e3\/d82\/4a2\/6e3d824a237426ac365ef3643270026e.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now we select an arbitrary vertex (A ) as a starting vertex and visit it. Then we set its level as &#8216;Lo&#8217;. At zero level (Lo), we have one vertex (A).  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/1dc\/258\/d4b\/1dc258d4b204d9e555bc0033b3f2ca38.jpeg\" width=\"321\" height=\"223\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1dc\/258\/d4b\/1dc258d4b204d9e555bc0033b3f2ca38.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>For all vertices in level zero, we will go to each undiscovered edge. Every undiscovered edge follows with another vertex. For the vertex that follows is unvisited, then we will visit that vertex and add it to the next level. And if that vertex is visited then we will set the edge to be a cross edge.<\/p>\n<p>Now we go to the first undiscovered edge &#8216;B&#8217; and make it discover edge from the discovered vertex &#8216;A&#8217;. Discovery edge is represented by black dotted lines. Similarly, we visit undiscover edges C and D and make them discovered edges.\u00a0 Also, we add B, C and D edges to level 1 (L1).<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/1cf\/003\/b48\/1cf003b4855caab7c26854e0bc836f82.jpeg\" width=\"344\" height=\"222\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1cf\/003\/b48\/1cf003b4855caab7c26854e0bc836f82.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now there are no more edges to traverse for Lo. So, we can go to the next level L1. Now we will go through each vertex of L1. At vertex B, we go to each of the undiscovered edges. From vertex B, we will reach vertex C which has already been visited. So now we will set edge C as a cross edge. The cross edge is represented by the blue line.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/4a1\/676\/c63\/4a1676c63e1799a181cf1741f1dcd3c2.jpeg\" width=\"350\" height=\"227\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4a1\/676\/c63\/4a1676c63e1799a181cf1741f1dcd3c2.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now, we go to undiscovered edge E from vertex B.E is the unvisited vertex. So we visit the vertex E and discover the edge. Then E has added to Level 2 ( L2 ) and comes back to B.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/691\/d96\/48a\/691d9648a6653006484a4f73cfab59c0.jpeg\" width=\"351\" height=\"233\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/691\/d96\/48a\/691d9648a6653006484a4f73cfab59c0.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Then we go to vertex C where there are three undiscovered edges( E, F and D ). As E is already visited, so we make it cross edge with a blue line. Now we will go to vertex F that is unvisited, so we make this edge a discovery edge. Now we go to edge D that is already visited, so we make it cross edge.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/c97\/981\/1fc\/c979811fce5e1d4d32ab90bba6033636.jpg\" width=\"343\" height=\"227\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c97\/981\/1fc\/c979811fce5e1d4d32ab90bba6033636.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now D has left one undiscovered edge F. It can be observed that F has been already visited so it will become cross-edged with D.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/c9d\/3c7\/c63\/c9d3c7c63efcbbf540bdd658875d5401.jpg\" width=\"342\" height=\"235\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c9d\/3c7\/c63\/c9d3c7c63efcbbf540bdd658875d5401.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Next, we go to level L2 that contains E and F vertices. On E, there are no undiscovered vertices. Now we go to F where there are also no undiscovered vertices. So now level L2 will also complete. So, now traversing has been completed. And the breadth-first search has been done.  <\/p>\n<p><strong>Pseudocode<\/strong><\/p>\n<p>Let us consider Graph &#8216;A&#8217; as input and called our algorithm BS. Firstly, we will define all vertices are unvisited and all edges are undiscovered.  <\/p>\n<pre><code class=\"cpp\">BS(A){ for all v  A.vertices{ setlabel( v , UV )    } for all e  A.vertices{ setlabel( e , UD )    } for B A.vertices{           list.addEnd(B);     setlabel(B,V);     }       while ( list.Notempty( ) ){ v = list.removeFront( );   } for e A.incident on v{ if ( e.label == UD ){ q = adjvertex(v,e);     } if ( q.label = V ){ setlablel( e, cross); } if ( q.label == UV ){ setlablel( e, D);   setlabel( q , V ); list.addEnd(q); } } }<\/code><\/pre>\n<p><strong>Time Complexity of Breadth-First Search<\/strong><\/p>\n<p>Its time complexity is\u00a0   <\/p>\n<p>                                                                              <em>b^x  <\/em><\/p>\n<p>Where b represents the branching factor and x is level.  <\/p>\n<p><strong>Space Complexity of Breadth-First Search<\/strong><\/p>\n<p>Its space complexity is :   <\/p>\n<p>                                                                              <em> b^x  <\/em><\/p>\n<p>Where b represents the branching factor and x is level.  <\/p>\n<p><strong>Advantages of Breadth-First Search<\/strong><\/p>\n<p>It has the following advantages:<\/p>\n<ul>\n<li>\n<p>BFS will not get trapped exploring visually impaired search.<\/p>\n<\/li>\n<li>\n<p>If there are several solutions, then it will give a cost-efficient solution because a longer route is never investigated until all shorter paths are already available.<\/p>\n<\/li>\n<li>\n<p>With this search method, we can find the final solution without examining very much of the search room at all.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Disadvantages of Breadth-First Search<\/strong><\/p>\n<p>It has the following disadvantages:<\/p>\n<ul>\n<li>\n<p>The amount of time required to produce all the nodes is to be taken into consideration because of time complexity.<\/p>\n<\/li>\n<li>\n<p>It uses plenty of memory space.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Applications of Breadth-First Search<\/strong><\/p>\n<p>It has the following applications:<\/p>\n<ul>\n<li>\n<p>It is used to find the shortest path in the undirected graph.<\/p>\n<\/li>\n<li>\n<p>It is used in cycle detection.<\/p>\n<\/li>\n<li>\n<p>It is used in the bipartite check.<\/p>\n<\/li>\n<li>\n<p>It is used in social networking websites and GPS navigation.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Depth First Search (DFS)<\/strong><\/p>\n<p>It is a way to traverse the graph. In this, we visit all the vertices and edges and traverse the graph. In depth-first search, the stack data structure is used that follows the LIFO( Last In and First Out) principle. Depth-first search produces a non-optimal solution. In depth-first search, we keep on exploring or visiting vertices till we reach a dead-end where there are no more edges to traverse from that vertex and then we backtrack.   <\/p>\n<p><strong>Implementation of Depth First Search<\/strong><\/p>\n<p>Implementation of depth-first search involves following major steps:<\/p>\n<ul>\n<li>\n<p>Firstly select an arbitrary vertex and make it the current vertex by visiting it.<\/p>\n<\/li>\n<li>\n<p>Then look for undiscovered edges corresponding to the current vertex.<\/p>\n<\/li>\n<li>\n<p>On finding the undiscovered edge, we see whether the vertex that follows is an unvisited vertex or not.<\/p>\n<\/li>\n<li>\n<p>If it is an unvisited vertex, we set a discovery edge and then go to that vertex.<\/p>\n<\/li>\n<li>\n<p>If it is a visited vertex, we set it as a back edge.<\/p>\n<\/li>\n<li>\n<p>If there is no undiscovered edge found, we must backtrack. <\/p>\n<\/li>\n<\/ul>\n<p><strong>Example<\/strong><\/p>\n<p>Let us consider the graph shown below. Initially, all the vertices are unvisited, and all edges are undiscovered. In this graph, we have represented an unvisited vertex by a circle and undiscovered edge by a single line.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/c18\/63f\/355\/c1863f355bd7d187496919d7c21e2ab1.jpg\" width=\"388\" height=\"212\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c18\/63f\/355\/c1863f355bd7d187496919d7c21e2ab1.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Firstly, we choose an arbitrary vertex A and visit it. The visited vertex is represented by a green circle while the current vertex by a red circle.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/65f\/e3f\/1d1\/65fe3f1d1c46c9d0c2af44423c1435b7.jpg\" width=\"388\" height=\"210\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/65f\/e3f\/1d1\/65fe3f1d1c46c9d0c2af44423c1435b7.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now we look for corresponding edges of vertex A. Vertex A has four undiscovered edges B, D, C and E. From the current vertex A, we will take B as an undiscovered edge and visit it. Then we will set the edge traversed to discovered. Then B will become the current vertex after visiting it. And edge between A and B will become discovered edge that is represented by a dotted line.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/a9b\/ac4\/dcb\/a9bac4dcbc68edd652b7e74d49fc3ec3.jpg\" width=\"389\" height=\"213\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a9b\/ac4\/dcb\/a9bac4dcbc68edd652b7e74d49fc3ec3.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now from current vertex B, there is one undiscovered edge C. So we will visit C and discovered it. Then C will become the current vertex.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/ccc\/64e\/7f6\/ccc64e7f6c8457f76da9741a077faad1.jpeg\" width=\"397\" height=\"223\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ccc\/64e\/7f6\/ccc64e7f6c8457f76da9741a077faad1.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now, we will look for undiscovered edges from current vertex C. If we consider a discovered edge from C to A, it can be seen that an undiscovered edge is leading to an already visited vertex. If the vertex that follows the undiscovered edge is visited, then mark the edge as the back edge. And back edges are represented by a blue colour line. So, the edge between A and C will become a back edge.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/bad\/957\/4d5\/bad9574d5f4f8a0b4f9bd340626d19e0.jpg\" width=\"391\" height=\"202\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bad\/957\/4d5\/bad9574d5f4f8a0b4f9bd340626d19e0.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>From current vertex C, we move on to visit undiscovered edge D and make it visited. Now D will become the current vertex.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/c58\/893\/fa6\/c58893fa6b993bdad6ff4de14dae1c38.jpg\" width=\"400\" height=\"215\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c58\/893\/fa6\/c58893fa6b993bdad6ff4de14dae1c38.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>From D, there is one undiscovered edge A, but it reaches the visited vertex. So we will convert this edge into a back edge.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/27a\/372\/4aa\/27a3724aae10c17cafb37f35fa2e2d35.jpg\" width=\"397\" height=\"206\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/27a\/372\/4aa\/27a3724aae10c17cafb37f35fa2e2d35.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now from current vertex D, there is left no undiscovered edge. So in such a case, we will set current vertex C which is the parent vertex of D.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/2b3\/d1d\/7dc\/2b3d1d7dc0e1a2c1679ae53e71b524ea.jpg\" width=\"402\" height=\"216\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2b3\/d1d\/7dc\/2b3d1d7dc0e1a2c1679ae53e71b524ea.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>From current vertex C, we have one undiscovered edge E. So we will visit vertex E and it will become the current vertex.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/596\/de2\/1c3\/596de21c37fc1e04fad075c736a8aa9c.jpg\" width=\"404\" height=\"214\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/596\/de2\/1c3\/596de21c37fc1e04fad075c736a8aa9c.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now from vertex E, there is one undiscovered edge A. As vertex A has been already visited. So edge between E and A will become a back edge.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/925\/277\/726\/9252777266ddd1b0ef31997632c598a4.jpg\" width=\"398\" height=\"216\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/925\/277\/726\/9252777266ddd1b0ef31997632c598a4.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now we will backtrack from E to C because E has left no undiscovered edges.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/f45\/148\/4b8\/f451484b861f214f701761b8927778ff.jpg\" width=\"384\" height=\"207\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f45\/148\/4b8\/f451484b861f214f701761b8927778ff.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now we will backtrack from C to B because C has left no undiscovered edge.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/769\/3dc\/f0c\/7693dcf0c9a93386b8a15d0469694dfb.jpg\" width=\"390\" height=\"207\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/769\/3dc\/f0c\/7693dcf0c9a93386b8a15d0469694dfb.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now B has left with undiscovered edges so we will backtrack from B to A. Now all the vertices have been visited. And traversing has been completed.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/92d\/eaa\/590\/92deaa5905152b64c81050ea0ae6d49f.jpg\" width=\"388\" height=\"212\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/92d\/eaa\/590\/92deaa5905152b64c81050ea0ae6d49f.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Pseudocode <\/strong><\/p>\n<p>Let us consider Graph &#8216;A&#8217; as input and called our algorithm DS. Firstly, we will define all vertices are unvisited and all edges are undiscovered.  <\/p>\n<pre><code class=\"cpp\">DS(A){   for v  A.vertices{     setlabel ( v, UN );  } for e  A.edges{ setlabel ( e, UD ); } for v  A.vertices{ visit( v, A) ;   } setlabel ( v , V );  for e  v.incidentEdges{ if(e.label == UD){ q = adjacentVertex ( v, e );     } if(q.label == UV){ setlabel(e, D);   visit( q, A); } if(q.label == V){ setlabel(e, B);   } } }<\/code><\/pre>\n<p><strong>Time Complexity of Depth First Search<\/strong><\/p>\n<p>Its time complexity is\u00a0   <\/p>\n<p>                                                                           <em>O(n^x)<\/em> <em> <\/em><\/p>\n<p>Where n represents the number of nodes at level x.  <\/p>\n<p><strong>Space Complexity of Depth First Search<\/strong><\/p>\n<p>Its space complexity is   <\/p>\n<p><em>                                                                            O(n*x) <\/em> <\/p>\n<p>Where n represents the number of nodes at level x.  <\/p>\n<p><strong>Advantages of Depth First Search<\/strong><\/p>\n<p>It has the following advantages:<\/p>\n<ul>\n<li>\n<p>It needs less amount of memory because just the nodes on the current path will be stored.<\/p>\n<\/li>\n<li>\n<p>With this search method, we can find the final solution without investigating very much of the search space at all.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Disadvantages of Depth First Search<\/strong><\/p>\n<p>It has the following disadvantages:<\/p>\n<ul>\n<li>\n<p>DFS cannot find many a satisfactory solution if they exist.<\/p>\n<\/li>\n<li>\n<p>Cut of depth, we have to define otherwise DFS goes in an infinite loop.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Applications of Depth First Search<\/strong><\/p>\n<p>It has the following applications:<\/p>\n<ul>\n<li>\n<p>It is used to find a minimum spanning tree.<\/p>\n<\/li>\n<li>\n<p>It is used in cycle detection.<\/p>\n<\/li>\n<li>\n<p>It is used in the bipartite check.<\/p>\n<\/li>\n<li>\n<p>Also used to check the path between two nodes.<\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/558806\/\"> https:\/\/habr.com\/ru\/articles\/558806\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>A graph is a kind of data structure that includes a set of vertices and edges. Graph traversing means a visit to each vertex of the graph precisely. The graph traversing is used to determine the order in which vertices are being visited throughout the search process. A graph traversing searches for the edges that will be used in the search operation without establishing loops. This means that using graph traversal, we will go to all the vertices of the graph without going into a looping path.<\/p>\n<p>There are two kinds of graph traversal methods.<\/p>\n<ul>\n<li>\n<p>Breadth-First Search<\/p>\n<\/li>\n<li>\n<p>Depth First Search<\/p>\n<\/li>\n<\/ul>\n<p><strong>Breadth-First Search (BFS)<\/strong><\/p>\n<p>Breadth-first search is also called a level order traversal. Breadth-first search is an algorithm to traverse the graph level by level. In the traversing process, we have to visit all vertices and edges. In this, we can take any node as a root node during traversal starting. For BFS, a queue data structure would be used that follows FIFO(First In First Out) principle. We visit nodes level wise. First, we complete the top level and then move on to lower levels.<\/p>\n<p>In breadth-first search, we identify the levels in the graph and then we visit or traverse all the vertices. Breadth-first search is level by level exploration of the graph.<\/p>\n<p><strong>Implementation of Breadth-First Search<\/strong><\/p>\n<p>The implementation of breadth-first search involves the following steps:<\/p>\n<ul>\n<li>\n<p>We take input as a graph to traverse it.<\/p>\n<\/li>\n<li>\n<p>For all edges incident on that vertex, we are going to check to see whether it is undiscovered or not. If it is an undiscovered edge, we check the vertex follows the undiscovered edge. If that vertex is visited, we mark the edge as a cross edge. If that vertex is not visited then we mark the edge as a discovered edge. We visit that vertex and add that vertex to the next level. Once none of the vertex incidents on the vertex is undiscovered, we start to explore the next vertex.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Example<\/strong><\/p>\n<p>Let us consider a graph shown below to traverse. At the beginning of the breadth-first search, all the vertices are going to be unvisited and all the edges are going to be undiscovered. So, we will symbolize the unvisited vertex by ( O ) and the undiscovered edge by ( \/ ).<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now we select an arbitrary vertex (A ) as a starting vertex and visit it. Then we set its level as &#8216;Lo&#8217;. At zero level (Lo), we have one vertex (A).  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>For all vertices in level zero, we will go to each undiscovered edge. Every undiscovered edge follows with another vertex. For the vertex that follows is unvisited, then we will visit that vertex and add it to the next level. And if that vertex is visited then we will set the edge to be a cross edge.<\/p>\n<p>Now we go to the first undiscovered edge &#8216;B&#8217; and make it discover edge from the discovered vertex &#8216;A&#8217;. Discovery edge is represented by black dotted lines. Similarly, we visit undiscover edges C and D and make them discovered edges.\u00a0 Also, we add B, C and D edges to level 1 (L1).<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now there are no more edges to traverse for Lo. So, we can go to the next level L1. Now we will go through each vertex of L1. At vertex B, we go to each of the undiscovered edges. From vertex B, we will reach vertex C which has already been visited. So now we will set edge C as a cross edge. The cross edge is represented by the blue line.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now, we go to undiscovered edge E from vertex B.E is the unvisited vertex. So we visit the vertex E and discover the edge. Then E has added to Level 2 ( L2 ) and comes back to B.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Then we go to vertex C where there are three undiscovered edges( E, F and D ). As E is already visited, so we make it cross edge with a blue line. Now we will go to vertex F that is unvisited, so we make this edge a discovery edge. Now we go to edge D that is already visited, so we make it cross edge.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now D has left one undiscovered edge F. It can be observed that F has been already visited so it will become cross-edged with D.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Next, we go to level L2 that contains E and F vertices. On E, there are no undiscovered vertices. Now we go to F where there are also no undiscovered vertices. So now level L2 will also complete. So, now traversing has been completed. And the breadth-first search has been done.  <\/p>\n<p><strong>Pseudocode<\/strong><\/p>\n<p>Let us consider Graph &#8216;A&#8217; as input and called our algorithm BS. Firstly, we will define all vertices are unvisited and all edges are undiscovered.  <\/p>\n<pre><code class=\"cpp\">BS(A){ for all v  A.vertices{ setlabel( v , UV )    } for all e  A.vertices{ setlabel( e , UD )    } for B A.vertices{           list.addEnd(B);     setlabel(B,V);     }       while ( list.Notempty( ) ){ v = list.removeFront( );   } for e A.incident on v{ if ( e.label == UD ){ q = adjvertex(v,e);     } if ( q.label = V ){ setlablel( e, cross); } if ( q.label == UV ){ setlablel( e, D);   setlabel( q , V ); list.addEnd(q); } } }<\/code><\/pre>\n<p><strong>Time Complexity of Breadth-First Search<\/strong><\/p>\n<p>Its time complexity is\u00a0   <\/p>\n<p>                                                                              <em>b^x  <\/em><\/p>\n<p>Where b represents the branching factor and x is level.  <\/p>\n<p><strong>Space Complexity of Breadth-First Search<\/strong><\/p>\n<p>Its space complexity is :   <\/p>\n<p>                                                                              <em> b^x  <\/em><\/p>\n<p>Where b represents the branching factor and x is level.  <\/p>\n<p><strong>Advantages of Breadth-First Search<\/strong><\/p>\n<p>It has the following advantages:<\/p>\n<ul>\n<li>\n<p>BFS will not get trapped exploring visually impaired search.<\/p>\n<\/li>\n<li>\n<p>If there are several solutions, then it will give a cost-efficient solution because a longer route is never investigated until all shorter paths are already available.<\/p>\n<\/li>\n<li>\n<p>With this search method, we can find the final solution without examining very much of the search room at all.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Disadvantages of Breadth-First Search<\/strong><\/p>\n<p>It has the following disadvantages:<\/p>\n<ul>\n<li>\n<p>The amount of time required to produce all the nodes is to be taken into consideration because of time complexity.<\/p>\n<\/li>\n<li>\n<p>It uses plenty of memory space.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Applications of Breadth-First Search<\/strong><\/p>\n<p>It has the following applications:<\/p>\n<ul>\n<li>\n<p>It is used to find the shortest path in the undirected graph.<\/p>\n<\/li>\n<li>\n<p>It is used in cycle detection.<\/p>\n<\/li>\n<li>\n<p>It is used in the bipartite check.<\/p>\n<\/li>\n<li>\n<p>It is used in social networking websites and GPS navigation.<\/p>\n<\/li>\n<\/ul>\n<p><strong>Depth First Search (DFS)<\/strong><\/p>\n<p>It is a way to traverse the graph. In this, we visit all the vertices and edges and traverse the graph. In depth-first search, the stack data structure is used that follows the LIFO( Last In and First Out) principle. Depth-first search produces a non-optimal solution. In depth-first search, we keep on exploring or visiting vertices till we reach a dead-end where there are no more edges to traverse from that vertex and then we backtrack.   <\/p>\n<p><strong>Implementation of Depth First Search<\/strong><\/p>\n<p>Implementation of depth-first search involves following major steps:<\/p>\n<ul>\n<li>\n<p>Firstly select an arbitrary vertex and make it the current vertex by visiting it.<\/p>\n<\/li>\n<li>\n<p>Then look for undiscovered edges corresponding to the current vertex.<\/p>\n<\/li>\n<li>\n<p>On finding the undiscovered edge, we see whether the vertex that follows is an unvisited vertex or not.<\/p>\n<\/li>\n<li>\n<p>If it is an unvisited vertex, we set a discovery edge and then go to that vertex.<\/p>\n<\/li>\n<li>\n<p>If it is a visited vertex, we set it as a back edge.<\/p>\n<\/li>\n<li>\n<p>If there is no undiscovered edge found, we must backtrack. <\/p>\n<\/li>\n<\/ul>\n<p><strong>Example<\/strong><\/p>\n<p>Let us consider the graph shown below. Initially, all the vertices are unvisited, and all edges are undiscovered. In this graph, we have represented an unvisited vertex by a circle and undiscovered edge by a single line.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Firstly, we choose an arbitrary vertex A and visit it. The visited vertex is represented by a green circle while the current vertex by a red circle.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now we look for corresponding edges of vertex A. Vertex A has four undiscovered edges B, D, C and E. From the current vertex A, we will take B as an undiscovered edge and visit it. Then we will set the edge traversed to discovered. Then B will become the current vertex after visiting it. And edge between A and B will become discovered edge that is represented by a dotted line.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now from current vertex B, there is one undiscovered edge C. So we will visit C and discovered it. Then C will become the current vertex.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now, we will look for undiscovered edges from current vertex C. If we consider a discovered edge from C to A, it can be seen that an undiscovered edge is leading to an already visited vertex. If the vertex that follows the undiscovered edge is visited, then mark the edge as the back edge. And back edges are represented by a blue colour line. So, the edge between A and C will become a back edge.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>From current vertex C, we move on to visit undiscovered edge D and make it visited. Now D will become the current vertex.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>From D, there is one undiscovered edge A, but it reaches the visited vertex. So we will convert this edge into a back edge.<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now from current vertex D, there is left no undiscovered edge. So in such a case, we will set current vertex C which is the parent vertex of D.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>From current vertex C, we have one undiscovered edge E. So we will visit vertex E and it will become the current vertex.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now from vertex E, there is one undiscovered edge A. As vertex A has been already visited. So edge between E and A will become a back edge.<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now we will backtrack from E to C because E has left no undiscovered edges.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now we will backtrack from C to B because C has left no undiscovered edge.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Now B has left with undiscovered edges so we will backtrack from B to A. Now all the vertices have been visited. And traversing has been completed.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p><strong>Pseudocode <\/strong><\/p>\n<p>Let us consider Graph &#8216;A&#8217; as input and called our algorithm DS. Firstly, we will define all vertices are unvisited and all edges are undiscovered.  <\/p>\n<pre><code class=\"cpp\">DS(A){   for v  A.vertices{     setlabel ( v, UN );  } for e  A.edges{ setlabel ( e, UD ); } for v  A.vertices{ visit( v, A) ;   } setlabel ( v , V );  for e  v.incidentEdges{ if(e.label == UD){ q = adjacentVertex ( v, e );     } if(q.label == UV){ setlabel(e, D);   visit( q, A); } if(q.label == V){ setlabel(e, B);   } } }<\/code><\/pre>\n<p><strong>Time Complexity of Depth First Search<\/strong><\/p>\n<p>Its time complexity is\u00a0   <\/p>\n<p>                                                                           <em>O(n^x)<\/em> <em> <\/em><\/p>\n<p>Where n represents the number of nodes at level x.  <\/p>\n<p><strong>Space Complexity of Depth First<\/strong><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-405541","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/405541","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=405541"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/405541\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=405541"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=405541"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=405541"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}