BFS vs DFS Graph Search Algorithms in Python

gubatron

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”/]

 

Related Posts

GRADLE: How to add a list of local .jar files to the build classpath

Sometimes you don’t want/cant use maven repos, all you have is a bunch of local jars on disk that you want to use as part of your compilation classpath, and the freaking gradle documentation is too vague. Here is an example: [pastacode lang=”java” manual=”dependencies%20%7B%0Acompile%20files(%E2%80%98lib%2Fjars%2Fgettext-commons.jar%E2%80%99%2C%0A%E2%80%98lib%2Fjars%2Flucene-3.5.0.jar%E2%80%99%2C%0A%E2%80%98lib%2Fjaudiotagger.jar%E2%80%99%2C%0A%E2%80%98lib%2Fjars%2Fh2-1.3.164.jar%E2%80%99%2C%0A%E2%80%98lib%2Fjars%2Fmessages.jar%E2%80%99%2C%0A%E2%80%98lib%2Fjars%2Fslf4j-api-1.7.5.jar%E2%80%99%2C%0A%E2%80%98lib%2Fjars%2Fjaudiotagger.jar%E2%80%99%2C%0A%E2%80%98lib%2Fjars%2Fmetadata-extractor-2.6.2.jar%E2%80%99%0A)%0A%7D” message=”” highlight=”” provider=”manual”/]

Accessing and manipulating a 32bit integer as a byte array in C++ using unions

I don’t think I’ve ever used union for anything, but today I came across a very interesting use case to avoid bit-shifting tricks when dealing with data embedded in numbers. What’s a union? Microsoft defines it this way A union is a user-defined type in which all members share the same memory location. This definition means that […]

How to filter logs in lighttpd

I usually don’t keep lighttpd access logs turned on to avoid writing for every read, but there are times when you need to monitor what’s going on, and you’d like to have a high signal-to-noise ratio so it might be convenient to ignore all requests to .gif, .png, .jpg, .css, .ico and other urls on […]

6 thoughts on “BFS vs DFS Graph Search Algorithms in Python”

  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.

    Reply

  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 🙂

    Reply

  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.

    Reply

  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?

    Reply

  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

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *