3
$\begingroup$

The most trivial implementation of BFS would simply store the last frontier (open list), build the new frontier, and then replace the last frontier with the new (like in the example python code below). But almost universally, the first algorithm shown for BFS in textbooks is the queue-based implementation.

What's the disadvantage of the simple frontier-storing approach? I can see it might use slightly more memory (effectively storing the new frontier while the old is still in memory), but usually textbooks only care about big-O complexity. Is there any other problem with it?

# example of a graph
g = {1: [2, 3], 2: [1, 3], 3: [1, 2, 4], 4: []}

def bfs(g, root):
    yield root
    boundary = [root]
    visited = {root}
    while boundary:
        new_boundary = []
        for v in boundary:
            for w in g[v]:
                if w not in visited:
                    yield w
                    visited.add(w)
                    new_boundary.append(w)
        boundary = new_boundary
$\endgroup$
3
$\begingroup$

Your analysis is correct. There is no major disadvantage of the two-list approach you outline.

One nice thing about the queue-based formulation of BFS is that it makes it easier to see the relationship to DFS and Dijkstra's algorithm. Start with the queue-based formulation, and replace the queue with a stack, and you get DFS. Replace the queue with a priority queue, and you get Dijkstra's algorithm. This similarity is aesthetically pleasing and might help understand the algorithm better.

A slight disadvantage of your two-list based scheme is that it has somewhat higher memory consumption: only a constant factor higher, so maybe not a big deal, but it is somewhat higher. This is because when you're traversing the current frontier, you keep around the items in the list that you've already traversed even after you've finished traversing them. In contrast, the queue-based method doesn't do that.

Nonetheless, in the big picture, you are absolutely right; both methods are pretty similar and there's not an overwhelming reason to prefer one over the other.

$\endgroup$
  • $\begingroup$ That makes sense. I also like the similarity between DFS/BFS/Dijkstra achieved with stack/queue/pqueue, but it seems one has to be careful to actually achieve the DFS/BFS equivalence. $\endgroup$ – max Oct 30 '16 at 17:59
  • 1
    $\begingroup$ "A slight disadvantage of your two-list based scheme is that it has somewhat higher memory consumption" - only for directed graphs. For undirected graphs, the previous/current/next frontier approach allows you to get rid of the visited set, which can be a major memory save, particularly for searches that generate the graph as they search it. $\endgroup$ – user2357112 Oct 30 '16 at 19:28
  • 1
    $\begingroup$ @user2357112, interesting, I hadn't noticed that! Seems like there are two small points to mention: 1. To achieve these savings, we need to save 3 lists (current, next, and previous), not just 2 (current and next). 2. This may or may not be a win, depending on how the size of the frontier compares to the number of vertices. One nice thing about a visited set is that there are ways to store the visited set more efficiently (e.g., using Bloom filters) -- it only saves a constant factor, and does require more sophisticated data structures, but this is used in the model checking world. $\endgroup$ – D.W. Oct 30 '16 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.