in Code

BFS vs DFS Graph Search Algorithms in Python

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
[python]
GRAPH = {1 : [2,3], 2:[4,5], 3:[6], 4:None, 5:[7,8], 6:None, 7:None, 8:None}

def BFS(start, target, GRAPH):
‘Use a QUEUE to search.’
print "Source:",source,"Target:",target
queue = [start]
visited = []

while len(queue) > 0:
x = queue.pop(0)

if x == target:
visited.append(x)
return visited
elif x not in visited:
visited = visited+[x]
if GRAPH[x] is not None:
‘add nodes at the END of the queue’
queue = queue + GRAPH[x]

return visited

def DFS(start, target, GRAPH):
‘Use a STACK to search.’
print "Source:",source,"Target:",target
stack = [start]
visited = []

while len(stack) > 0:
x = stack.pop(0)

if x == target:
visited.append(x)
return visited
elif x not in visited:
visited = visited+[x]
if GRAPH[x] is not None:
‘add nodes at the top of the stack’
stack = GRAPH[x] + stack

return visited

print "BFS Path",BFS(1,7,GRAPH)
print "DFS Path",DFS(1,7,GRAPH)
print "="*80
print "BFS Path",BFS(1,3,GRAPH)
print "DFS Path",DFS(1,3,GRAPH)
[/python]

Output
[bash]
$ python graph.py
BFS Path Source: 1 Target: 7
[1, 2, 3, 4, 5, 6, 7]
DFS Path Source: 1 Target: 7
[1, 2, 4, 5, 7]
================================================================================
BFS Path Source: 1 Target: 3
[1, 2, 3]
DFS Path Source: 1 Target: 3
[1, 2, 4, 5, 7, 8, 3]
[/bash]

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  1. 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.

  2. 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 🙂

  3. 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.

  4. 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?

  5. 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

Webmentions

  • c# - La ricerca di un particolare elemento in una pila November 3, 2015

    […] interessato al porting questo codice Python per C++. Come parte del porto, sto usando std::stack dal <stack> intestazione. Come è […]