{"id":43,"date":"2021-02-18T17:52:10","date_gmt":"2021-02-18T17:52:10","guid":{"rendered":"http:\/\/danielpgleason.com\/?p=43"},"modified":"2021-02-22T14:13:04","modified_gmt":"2021-02-22T14:13:04","slug":"breadth-first-search","status":"publish","type":"post","link":"https:\/\/danielpgleason.com\/index.php\/2021\/02\/18\/breadth-first-search\/","title":{"rendered":"Breadth First Search"},"content":{"rendered":"\n<p>This is similar to what I was doing when I was researching DFS (Depth First Search), which you can see below here I posted a link to my other posting. <\/p>\n\n\n\n<figure class=\"wp-block-embed-wordpress wp-block-embed is-type-wp-embed is-provider-daniel-p-gleason\"><div class=\"wp-block-embed__wrapper\">\n<blockquote class=\"wp-embedded-content\" data-secret=\"DwoFQbHubj\"><a href=\"https:\/\/danielpgleason.com\/index.php\/2021\/02\/17\/implementing-dfs-depth-first-search-in-c\/\">Implementing DFS (Depth First Search) in C++<\/a><\/blockquote><iframe loading=\"lazy\" class=\"wp-embedded-content\" sandbox=\"allow-scripts\" security=\"restricted\" style=\"position: absolute; visibility: hidden;\" title=\"&#8220;Implementing DFS (Depth First Search) in C++&#8221; &#8212; Daniel P. Gleason\" src=\"https:\/\/danielpgleason.com\/index.php\/2021\/02\/17\/implementing-dfs-depth-first-search-in-c\/embed\/#?secret=KtwwfFKxKx#?secret=DwoFQbHubj\" data-secret=\"DwoFQbHubj\" width=\"525\" height=\"296\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" scrolling=\"no\"><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Alright so hopefully the DFS algorithm makes sense. It&#8217;s very simple once you got it. Once you got it, you got it! <\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>Breadth First Search is a little bit trickier, but don&#8217;t worry. It&#8217;s still easy to learn. For BFS, it might be implemented like this:<\/p>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism line-numbers lang-cpp\" data-file=\"bfs\" data-lang=\"C++\"><code>vector&lt;string&gt; breadthFirstSearch(vector&lt;string&gt; *array) {\n    queue&lt;Node*&gt; q;\n\t\tarray-&gt;push_back(name);\n\t\tq.push(this);\n\t\t\n\t\twhile (!q.empty())\n\t\t{\n\t\t\tNode* n = q.front();\n\t\t\tq.pop();\n\t\t\t\n\t\t\tfor (int i = 0; i &lt; n-&gt;children.size(); i++)\n\t\t\t{\n\t\t\t\tif (count(array-&gt;begin(), array-&gt;end(), n-&gt;children[i]-&gt;name) == 0)\n\t\t\t\t{\n\t\t\t\t\tarray-&gt;push_back(n-&gt;children[i]-&gt;name);\n\t\t\t\t\tq.push(n-&gt;children[i]);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\t\t\n    return *array;\n  }<\/code><\/pre><\/div>\n\n\n\n<p>In the above sample, this method will essentially print out all of the children of a graph in breadth first search. That is, level by level. However, in a real situation, you would simply return the node when you find what you are looking for. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>This is similar to what I was doing when I was researching DFS (Depth First Search), which you can see below here I posted a link to my other posting. Alright so hopefully the DFS algorithm makes sense. It&#8217;s very simple once you got it. Once you got it, you got it! Breadth First Search &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/danielpgleason.com\/index.php\/2021\/02\/18\/breadth-first-search\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Breadth First Search&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[11],"tags":[15,12,13,16,14,7],"class_list":["post-43","post","type-post","status-publish","format-standard","hentry","category-algorithms","tag-algorithms","tag-bfs","tag-breadth-first-search","tag-computer-science","tag-graphs","tag-interview-questions"],"_links":{"self":[{"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/posts\/43"}],"collection":[{"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/comments?post=43"}],"version-history":[{"count":2,"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/posts\/43\/revisions"}],"predecessor-version":[{"id":47,"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/posts\/43\/revisions\/47"}],"wp:attachment":[{"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/media?parent=43"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/categories?post=43"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/danielpgleason.com\/index.php\/wp-json\/wp\/v2\/tags?post=43"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}