Here are implementations of iterative BFS and DFS search algorithms in Python.<\/p>\n
These are just to illustrate the slight difference in implementation of these algorithms.<\/p>\n
Basically, if you want to go deep, with DFS, you can use a queue on which you’ll be adding the next elements to explore as you traverse the graph.
\nIf you want to scan around the current node, you can use a stack so that you keep looking at the closest elements before you move forward.<\/p>\n
These functions use and return a list of visited nodes. If you want to make this a little more efficient, you can mark nodes as visited using a dictionary, or if the nodes themselves can have a property added to them, you can use that instead so you don’t have to do a linear search every time you want to know if a node was visited or not. I left it like that again, to just focus on the algorithm itself and not in the performance optimizations.<\/p>\n
Source<\/strong><\/p>\n [pastacode lang=”python” manual=”GRAPH%20%3D%20%7B1%20%3A%20%5B2%2C3%5D%2C%202%3A%5B4%2C5%5D%2C%203%3A%5B6%5D%2C%204%3ANone%2C%205%3A%5B7%2C8%5D%2C%206%3ANone%2C%207%3ANone%2C%208%3ANone%7D%0A%0Adef%20BFS(start%2C%20target%2C%20GRAPH)%3A%0A%C2%A0%20’Use%20a%20QUEUE%20to%20search.’%0A%C2%A0%20print%20%22Source%3A%22%2Csource%2C%22Target%3A%22%2Ctarget%0A%C2%A0%20queue%20%3D%20%5Bstart%5D%0A%C2%A0%20visited%20%3D%20%5B%5D%0A%0A%C2%A0%20while%20len(queue)%20%3E%200%3A%0A%C2%A0%20%C2%A0%20x%20%3D%20queue.pop(0)%0A%0A%C2%A0%20%C2%A0%20if%20x%20%3D%3D%20target%3A%0A%C2%A0%20%C2%A0%20%C2%A0%20visited.append(x)%0A%C2%A0%20%C2%A0%20%C2%A0%20return%20visited%0A%C2%A0%20%C2%A0%20elif%20x%20not%20in%20visited%3A%0A%C2%A0%20%C2%A0%20%C2%A0%20visited%20%3D%20visited%2B%5Bx%5D%0A%C2%A0%20%C2%A0%20if%20GRAPH%5Bx%5D%20is%20not%20None%3A%0A%C2%A0%20%C2%A0%20%C2%A0%20’add%20nodes%20at%20the%20END%20of%20the%20queue’%0A%C2%A0%20%C2%A0%20%C2%A0%20queue%20%3D%20queue%20%2B%20GRAPH%5Bx%5D%0A%0A%C2%A0%20return%20visited%0A%0Adef%20DFS(start%2C%20target%2C%20GRAPH)%3A%0A%C2%A0%20’Use%20a%20STACK%20to%20search.’%0A%C2%A0%20print%20%22Source%3A%22%2Csource%2C%22Target%3A%22%2Ctarget%0A%C2%A0%20stack%20%3D%20%5Bstart%5D%0A%C2%A0%20visited%20%3D%20%5B%5D%0A%0A%C2%A0%20while%20len(stack)%20%3E%200%3A%0A%C2%A0%20%C2%A0%20x%20%3D%20stack.pop(0)%0A%0A%C2%A0%20%C2%A0%20if%20x%20%3D%3D%20target%3A%0A%C2%A0%20%C2%A0%20%C2%A0%20visited.append(x)%0A%C2%A0%20%C2%A0%20%C2%A0%20return%20visited%0A%C2%A0%20%C2%A0%20elif%20x%20not%20in%20visited%3A%0A%C2%A0%20%C2%A0%20%C2%A0%20visited%20%3D%20visited%2B%5Bx%5D%0A%C2%A0%20%C2%A0%20if%20GRAPH%5Bx%5D%20is%20not%20None%3A%0A%C2%A0%20%C2%A0%20%C2%A0%20’add%20nodes%20at%20the%20top%20of%20the%20stack’%0A%C2%A0%20%C2%A0%20%C2%A0%20stack%20%3D%20GRAPH%5Bx%5D%20%2B%20stack%0A%0A%C2%A0%20return%20visited%0A%0Aprint%20%22BFS%20Path%22%2CBFS(1%2C7%2CGRAPH)%0Aprint%20%22DFS%20Path%22%2CDFS(1%2C7%2CGRAPH)%0Aprint%20%22%3D%22*80%0Aprint%20%22BFS%20Path%22%2CBFS(1%2C3%2CGRAPH)%0Aprint%20%22DFS%20Path%22%2CDFS(1%2C3%2CGRAPH)” message=”” highlight=”” provider=”manual”\/]<\/p>\n Output<\/strong><\/p>\n [pastacode lang=”bash” manual=”%24%20python%20graph.py%0ABFS%20Path%20Source%3A%201%20Target%3A%207%0A%5B1%2C%202%2C%203%2C%204%2C%205%2C%206%2C%207%5D%0ADFS%20Path%20Source%3A%201%20Target%3A%207%0A%5B1%2C%202%2C%204%2C%205%2C%207%5D%0A%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%3D%0ABFS%20Path%20Source%3A%201%20Target%3A%203%0A%5B1%2C%202%2C%203%5D%0ADFS%20Path%20Source%3A%201%20Target%3A%203%0A%5B1%2C%202%2C%204%2C%205%2C%207%2C%208%2C%203%5D” message=”” highlight=”” provider=”manual”\/]<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" Here are implementations of iterative BFS and DFS search algorithms in Python. These are just to illustrate the slight difference in implementation of these algorithms. Basically, if you want to go deep, with DFS, you can use a queue on which you’ll be adding the next elements to explore as you traverse the graph. If […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","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},"jetpack_post_was_ever_published":false},"categories":[15],"tags":[],"class_list":["post-2568","post","type-post","status-publish","format-standard","hentry","category-code"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p5Unzf-Fq","jetpack-related-posts":[{"id":1114,"url":"https:\/\/www.gubatron.com\/blog\/using-a-linear-array-as-a-bidimensional-matrix\/","url_meta":{"origin":2568,"position":0},"title":"Using a linear array as a bidimensional matrix","author":"gubatron","date":"January 27, 2009","format":false,"excerpt":"Often times I find the need to use a list or linear array as if it was a table. Everytime I need to do so, I always end up coding functions to convert a (x,y) coordinate to the real index n in the array. Let me illustrate, with an example.\u2026","rel":"","context":"In "Code"","block_context":{"text":"Code","link":"https:\/\/www.gubatron.com\/blog\/category\/code\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":3922,"url":"https:\/\/www.gubatron.com\/blog\/python-in-functional-style-how-to-add-2-lists-of-integers-without-using-loops\/","url_meta":{"origin":2568,"position":1},"title":"Python in Functional Style: How to add 2 lists of integers without using loops","author":"gubatron","date":"January 27, 2021","format":false,"excerpt":"Usually you'd add a list of integers this way: [pastacode lang=\"python\" manual=\"a%20%3D%20%5B2%2C%202%2C%202%2C%202%5D%0Ab%20%3D%20%5B2%2C%202%2C%202%2C%202%5D%0Ac%20%3D%20%5B%5D%0Afor%20i%20in%20range(len(a))%3A%0A%20c.append(a%5Bi%5D%20%2B%20b%5Bi%5D)\" message=\"\" highlight=\"\" provider=\"manual\"\/] You can do it functionally without any loops in different ways: Using map and a lambda that adds them up [pastacode lang=\"python\" manual=\"c%20%3D%20list(map(lambda%20x%2Cy%3A%20x%2By%2C%20a%2C%20b))\" message=\"\" highlight=\"\" provider=\"manual\"\/] or you can import the add operator as a\u2026","rel":"","context":"In "Code"","block_context":{"text":"Code","link":"https:\/\/www.gubatron.com\/blog\/category\/code\/"},"img":{"alt_text":"Close End 10cm 80cm 5# 10pcs white Metal Zipper for Sewing ...","src":"https:\/\/external-content.duckduckgo.com\/iu\/?u=https%3A%2F%2Fae01.alicdn.com%2Fkf%2FHTB1x3GhNFXXXXaGXFXXq6xXFXXXu%2FClose-End-10cm-80cm-5-10pcs-white-Metal-Zipper-for-Sewing-zip-Garment-Accessories-Jeans-Zippers.jpg&f=1&nofb=1","width":350,"height":200},"classes":[]},{"id":2100,"url":"https:\/\/www.gubatron.com\/blog\/water-as-a-medium-of-intercontinental-data-transfer\/","url_meta":{"origin":2568,"position":2},"title":"Discussion: Water as a medium of Intercontinental High Speeds Data Transfer","author":"gubatron","date":"November 21, 2010","format":false,"excerpt":"If water can transfer sound (low frequencies) 4 times faster than air, can it do the same for higher frequencies? could you encode megabits\/s at an ideal physical frequency range and transmit it over rivers, seas, or even oceans? I'm thinking that the Air is probably one of the worst\u2026","rel":"","context":"In "Ideas"","block_context":{"text":"Ideas","link":"https:\/\/www.gubatron.com\/blog\/category\/ideas\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2767,"url":"https:\/\/www.gubatron.com\/blog\/ubuntu-packages-for-a-kick-ass-web-server\/","url_meta":{"origin":2568,"position":3},"title":"ubuntu packages for a kick ass web server","author":"gubatron","date":"September 7, 2012","format":false,"excerpt":"Copy and paste the following list on a file, say \"packages.txt\". To install all just do: sudo apt-get install $(cat packages.txt) accountsservice acpid adduser ant ant-optional apache2-utils apparmor apport apport-symptoms apt apt-transport-https apt-utils apt-xapian-index aptitude at base-files base-passwd bash bash-completion bc bind9-host bsdmainutils bsdutils busybox-initramfs busybox-static byobu bzip2 ca-certificates ca-certificates-java\u2026","rel":"","context":"In "Code"","block_context":{"text":"Code","link":"https:\/\/www.gubatron.com\/blog\/category\/code\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":3942,"url":"https:\/\/www.gubatron.com\/blog\/pascal-triangle-generator-in-python-and-then-in-haskell-the-gubatron-method\/","url_meta":{"origin":2568,"position":4},"title":"Pascal Triangle Generator in Python, and then in Haskell – The Gubatron Method","author":"gubatron","date":"May 6, 2021","format":false,"excerpt":"Here's in python, imperatively, and then in functional style without the need for loops. https:\/\/gist.github.com\/gubatron\/ed966ea4e614d6733715376ad5cfb85f Here's in Haskell, I call it the gubatron's method, explained in the comments. Saw it by looking at a pattern while trying to solve it in paper, it just clicked. Not sure if this is\u2026","rel":"","context":"In "Code"","block_context":{"text":"Code","link":"https:\/\/www.gubatron.com\/blog\/category\/code\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":273,"url":"https:\/\/www.gubatron.com\/blog\/snowrss\/","url_meta":{"origin":2568,"position":5},"title":"SnowRSS","author":"gubatron","date":"March 18, 2006","format":false,"excerpt":"SnowRSS SnowRSS is an RSS Aggregator engine I wrote in python (Licensed under the GPL). Currently it's been under use in wedoit4you.com and its stable. It can read RSS and ATOM feeds. It uses the feedparser python module, and the MySQLdb python module to do the job. DOWNLOAD You can\u2026","rel":"","context":"In "Gubatron"","block_context":{"text":"Gubatron","link":"https:\/\/www.gubatron.com\/blog\/category\/gubatron\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/posts\/2568","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/comments?post=2568"}],"version-history":[{"count":2,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/posts\/2568\/revisions"}],"predecessor-version":[{"id":3912,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/posts\/2568\/revisions\/3912"}],"wp:attachment":[{"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/media?parent=2568"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/categories?post=2568"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/tags?post=2568"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}