{"id":4083,"date":"2022-01-16T22:01:52","date_gmt":"2022-01-16T14:01:52","guid":{"rendered":"https:\/\/1989lifejourney.com\/?p=4083"},"modified":"2022-01-16T22:01:52","modified_gmt":"2022-01-16T14:01:52","slug":"breadth-first-search","status":"publish","type":"post","link":"https:\/\/1989lifejourney.com\/?p=4083","title":{"rendered":"Breadth-First Search"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><strong>Breadth-first search<\/strong>\u00a0(<strong>BFS<\/strong>) is an\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Algorithm\">algorithm<\/a>\u00a0for searching a\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Tree_(data_structure)\">tree<\/a>\u00a0data structure for a node that satisfies a given property. It starts at the\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Tree_(data_structure)#Terminology\">tree root<\/a>\u00a0and explores all nodes at the present\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Tree_(data_structure)#Terminology\">depth<\/a>\u00a0prior to moving on to the nodes at the next depth level. Extra memory, usually a\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Queue_(data_structure)\">queue<\/a>, is needed to keep track of the child nodes that were encountered but not yet explored.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Ref:<\/strong> <a href=\"https:\/\/en.wikipedia.org\/wiki\/Breadth-first_search\">https:\/\/en.wikipedia.org\/wiki\/Breadth-first_search<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\nclass Node {\n    var left: Node?\n    var right: Node?\n    var val: Int?\n    init(val: Int) {\n        self.val = val\n    }\n}\n\n\/\/ Establish tree\n\/\/          1\n\/\/       2    3\n\/\/     4  5  6  7\nlet n1 = Node(val: 1)\nlet n2 = Node(val: 2)\nlet n3 = Node(val: 3)\nlet n4 = Node(val: 4)\nlet n5 = Node(val: 5)\nlet n6 = Node(val: 6)\nlet n7 = Node(val: 7)\nn1.left = n2\nn1.right = n3\nn2.left = n4\nn2.right = n5\nn3.left = n6\nn3.right = n7\n\nfunc breadthFirstSearchIterative(root: Node?) {\n    guard let root = root else {\n        return\n    }\n    var queue: &#091;Node] = &#091;]\n    queue.append(root)\n    while !queue.isEmpty {\n        let n = queue.removeFirst()\n        print(n.val!)\n        if let right = n.right {\n            queue.append(right)\n        }\n        if let left = n.left {\n            queue.append(left)\n        }\n    }\n}\n\nbreadthFirstSearchIterative(root: n1)<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Breadth-first search\u00a0(BFS) is an\u00a0algorithm\u00a0for searchin [&hellip;]<\/p>\n","protected":false},"author":139426785,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":"","_postgate_lock_override":"inherit","_postgate_lock_mode":"inherit","_postgate_preview_mode":"inherit","_postgate_preview_limit":0,"_postgate_product_ids":[],"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":true,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_wpcom_ai_launchpad_first_post":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"post_folder":[],"class_list":["post-4083","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/paR5vw-13R","jetpack-related-posts":[{"id":4080,"url":"https:\/\/1989lifejourney.com\/?p=4080","url_meta":{"origin":4083,"position":0},"title":"Depth-First Search","author":"Kevin","date":"16 1 \u6708, 2022","format":false,"excerpt":"Depth-first search\u00a0(DFS) is an\u00a0algorithm\u00a0for trave\u2026","rel":"","context":"\u5728\u300cIOS Development\u300d\u4e2d","block_context":{"text":"IOS Development","link":"https:\/\/1989lifejourney.com\/?cat=37324612"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":13304,"url":"https:\/\/1989lifejourney.com\/?p=13304","url_meta":{"origin":4083,"position":1},"title":"Inside the Art Market: How It Works and How I See Art","author":"Kevin","date":"26 1 \u6708, 2026","format":false,"excerpt":"This is a PowerPoint presentation I made to introd\u2026","rel":"","context":"\u5728\u300cArt\u300d\u4e2d","block_context":{"text":"Art","link":"https:\/\/1989lifejourney.com\/?cat=177"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":11512,"url":"https:\/\/1989lifejourney.com\/?p=11512","url_meta":{"origin":4083,"position":2},"title":"2025\/2\/8 \u4e5d\u4efd\u91d1\u74dc\u77f3\u534a\u65e5\u904a","author":"Kevin","date":"1 3 \u6708, 2025","format":false,"excerpt":"\u5f9e\u5fe0\u5b5d\u5fa9\u82082\u865f\u51fa\u53e3\u65c1\u7684\u516c\u8eca\u7ad9\u724c\u51fa\u767c\uff0c\u67091062\u516c\u8eca\u53ef\u4ee5\u524d\u5f80\u4e5d\u4efd\u3002 p.s. 965\u516c\u8eca\u4e5f\u53ef\u4ee5\u5230\u4e5d\u4efd\uff0c\u2026","rel":"","context":"\u5728\u300cTravel\u300d\u4e2d","block_context":{"text":"Travel","link":"https:\/\/1989lifejourney.com\/?cat=200"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/03\/IMG_8752-1.jpeg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/03\/IMG_8752-1.jpeg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/03\/IMG_8752-1.jpeg?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/03\/IMG_8752-1.jpeg?resize=700%2C400&ssl=1 2x, https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/03\/IMG_8752-1.jpeg?resize=1050%2C600&ssl=1 3x, https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/03\/IMG_8752-1.jpeg?resize=1400%2C800&ssl=1 4x"},"classes":[]},{"id":12189,"url":"https:\/\/1989lifejourney.com\/?p=12189","url_meta":{"origin":4083,"position":3},"title":"App vs AI agent","author":"Kevin","date":"19 7 \u6708, 2025","format":false,"excerpt":"The first thing I did this morning was argue with \u2026","rel":"","context":"\u5728\u300cAI related\u300d\u4e2d","block_context":{"text":"AI related","link":"https:\/\/1989lifejourney.com\/?cat=763194612"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7878,"url":"https:\/\/1989lifejourney.com\/?p=7878","url_meta":{"origin":4083,"position":4},"title":"ChatGPT\u6e2c\u8a66_23 (Write the comment which style is Apple&#8217;s documentation comment style)","author":"Kevin","date":"12 4 \u6708, 2023","format":false,"excerpt":"\u554f\u984c: Write the comment for below Swift functions wh\u2026","rel":"","context":"\u5728\u300cChatGPT\u300d\u4e2d","block_context":{"text":"ChatGPT","link":"https:\/\/1989lifejourney.com\/?cat=760577830"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":12242,"url":"https:\/\/1989lifejourney.com\/?p=12242","url_meta":{"origin":4083,"position":5},"title":"A memory I wish I could go back to","author":"Kevin","date":"7 8 \u6708, 2025","format":false,"excerpt":"In the past, there was a memory I often wished I c\u2026","rel":"","context":"\u985e\u4f3c\u6587\u7ae0","block_context":{"text":"\u985e\u4f3c\u6587\u7ae0","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/4083","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/users\/139426785"}],"replies":[{"embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4083"}],"version-history":[{"count":1,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/4083\/revisions"}],"predecessor-version":[{"id":4084,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/4083\/revisions\/4084"}],"wp:attachment":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4083"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4083"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4083"},{"taxonomy":"post_folder","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fpost_folder&post=4083"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}