Python Breadth First Search optimisation

Question

Given this code...

import Queue

def breadthFirstSearch(graph, start, end):
    q = Queue.Queue()
    path = [start]
    q.put(path)
    while not q.empty():
        path = q.get()
        lastNode = path[len(path) - 1]
        if lastNode == end:
            return path
        for linkNode in graph[lastNode]:
            if linkNode not in path:
                newPath = []
                newPath = path + [linkNode]
                q.put(newPath)

Where graph is a dictionary representing a directed graph, eg, {'stack':['overflow'], 'foo':['bar']} ie, stack is pointing to overflow and foo is pointing to bar.

Can this breadth first search be optimised more? Because I am planning to use it on a very large dictionary.

While it's probably not a big optimization, Queue.Queue is intended for synchronization between multiple threads. If you just need a simple queue data structure, use collections.deque instead, and avoid the synchronization overhead. — Blckknght
– Blckknght, Commented May 25, 2013 at 7:57
When I use it, I get a different answer, I dont know why though... — Ogen
– Ogen, Commented May 25, 2013 at 8:31

Nolen Royalty · Accepted Answer · 2013-05-25 07:06:36Z

10

Why not keep a set of visited nodes so that you don't keep hitting the same nodes? This should work since it doesn't look like you're using a weighted graph. Something like this:

import Queue

def bfs(graph, start, end):
    q = Queue.Queue()
    path = [start]
    q.put(path)
    visited = set([start])

    while not q.empty():
        path = q.get()
        last_node = path[-1]
        if last_node == end:
            return path
        for node in graph[last_node]:
            if node not in visited:
                visited.add(node)
                q.put(path + [node])

edited May 25, 2013 at 7:06

answered May 25, 2013 at 7:00

Nolen Royalty

18.7k4 gold badges43 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Ogen Over a year ago

Thanks for the reply, im going to test it now and get back to you. Thanks again.

Ogen Over a year ago

I dont know why, but the code is getting stuck on the line: while not q.empty():

Nolen Royalty Over a year ago

@Clay I completely forgot to add path = q.get() to my code, that probably doesn't help...

Ogen Over a year ago

You are a genius. I tried it and it works so much faster now that I dont visit 100000+ nodes twice! Thank you very much :)

Tobia Over a year ago

As an aside, I think using collections.deque would make it even faster, because Queue.Queue is heavily synchronized, which in this case is only a burden. See this answer by Keith Gaughan.

|

Collectives™ on Stack Overflow

Python Breadth First Search optimisation

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related