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 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.
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.
Source
[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”/]
Output
[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”/]
Forgive me if I’m mistaken, but I don’t think your BFS works properly. BFS should return the shorted path, in your first example DFS returns a shorter path than BFS, that’s impossible.
I need to look at this again, wrote it a long time ago.
But your assumption based on the length of the paths has nothing to do with the correctness. Results may vary depending on the graph topology right?
However, you may have drawn the graph and seen an error 🙂
James it’s right. If you implement BFS to go from A to B, it will give you the shortest path because BFS computes in layers.
Note that for that given graph you do not have a 2-3 connection (for exemple), so [1, 2, 3, 4, 5, 6, 7] can never be a path from the graph.
I have the following error when i open it in python shell:
BFS Path Source:
Traceback (most recent call last):
File “…”, line 43, in
print “BFS Path”,BFS(1,7,GRAPH)
File “…”, line 5, in BFS
print “Source:”,source,”Target:”,target
NameError: global name ‘source’ is not defined
Why?
try renaming where it says ‘source’ to ‘start’
Hi man,
I think there is a mistake in your code. Even though data structures used are correct, it should be “stack = stack + GRAPH[x]” and “queue = GRAPH[x] + queue” instead, I tested. Let me know for your thoughts, thanks