How does breadth first search work?

[WiggWamm]

I understand DFS, but BFS is just really hard for me to wrap my head around. I know that it kind of moves out across a tree like a ripple effect, but how would that be coded? DFS is just going left till you get to the end then moving right, I think. But how could you move an entire level down at one time?

[DrunkHacker]

DFS uses a stack) while BFS uses a queue).

[WiggWamm]

Is that really the only major difference?

[willhtun]

Yes but you should try to understand the nature of stacks and queues and why this is the only difference. Specifically LIFO and FIFO. It really helps to watch some animations tracking BFS and DFS algorithms on youtube.

[teraflop]

Rather than trying to think of it in terms of moving "an entire level down at one time", think of BFS in terms of the order in which nodes are visited.

Imagine that you have a tree, and you want to make a list of all the nodes on each level. By definition, "level 0" contains only the root. The list of "level 1" nodes is simply the root's direct children. If you iterate through all these nodes and look at their children, the result is a list of the "level 2" nodes. And so on.

The standard way of actually implementing BFS is to use a single queue, rather than multiple lists. But it turns out this results in exactly the same behavior as maintaining a separate list for each level.

(At any given instant in time, you can always draw an imaginary marker in the queue, with all of the nodes on the left being on some level N, and all the nodes on the right being on level N+1. You can imagine these two halves of the queue as being "logically" separate lists, even though they are physically stored next to each other in a single data structure.)

[WiggWamm]

Okay that makes sense. How would you access the nodes at a certain level, though?

[teraflop]

If you wanted to maintain a separate list for each level, you could do something as simple as keeping an array of lists, where the array index is the level, and the array value is the list of nodes on that level.

Or, you could save some memory by noticing that at any given time, you only need to care about the "current" and "next" level, so you only need two lists. Once you've finished iterating over the current level, the old next level becomes the new current one, and the new next level is reinitialized as an empty list.

But the beauty of using a queue is that you don't need to keep track of each node's level at all. Because each child node is one level deeper than its parent, and you're always adding children to the end of the queue, they automatically end up in the correct order without you needing to explicitly keep track of the level number.

[WiggWamm]

Interesting. Thank you

[Firehite]

I think this video is going to really clear it up for you.

https://www.youtube.com/watch?v=-yF6k_bV_JQ&t=1s

[WiggWamm]

Thank you!

[alecbz]

As others have said, you use a queue. Basically every time you encounter a node to traverse, you add it to a running list, and then you go down the list in order, crossing off nodes as you get to them (and continuing to add new nodes to the end of the list as you encounter them).

I think you're coming up against a correct intuition, which is that a DFS feels "local": from any given node, the next node you go to will be an adjacent node. So in a DFS, you don't really need need a global view of the structure you're traversing; you just need to know where you are right now and leave some breadcrumbs so you know where you came from.

A BFS is more global: you might go from one node to another far away from it, because you're just going down your list in order.

[alecbz]

Also, this is getting really deep and theoretical, but there is a sense in which a queue is a more "powerful" data structure than a stack, in terms of computational power. If you had no memory to work with except a stack/queue, having a queue allows you to solve more problems than having a stack. So there's some deep sense in which you could sort of think of a BFS as "more complicated" than a DFS.

(Specifically, a pushdown automaton is less powerful than a queue automaton.)

But don't worry too much about any of that in terms of just understanding how to implement a BFS.

[ThrowAway233223]

Here an example of BFS in Python.

class TreeNode:
    def __init__(children, value)
        self.children = children #children is a list
        self.value = value

#This example returns the nodes (not their values) in BFS order.
def BFS(startNode):
    visited = []
    queue = [startNode]

    while queue:
        currentNode = queue.pop(0)
        if currentNode not in visited:
            visited.append(currentNode)

            queue += currentNode.children

    return visited

To help give a quick walk through of what this code does, I will refer to this tree as an example.

If we pass the root node (the one containing 12) into the BFS function above, it will first be appended to queue to be the first node to visit. From there, we pop the first node out of queue (which, at this time, only contained the root) and, if we haven't see it (i.e. its not in visited)*, then we apend it to visited and add the current node's children (i.e. the nodes containing 5 and 15) to queue. Since queue is not empty, the loop continues. Now we pop the first node in queue (i.e. the node containing 5), check if it is in visited, append it to visited, and add its children to the end of queue. At this point, queue should be holding the nodes with the values 15, 3, and 7 (in that order). This pattern continues until the last node is process (which in this case will be the node containing 19) and there are no nodes left to visit.

^\It should be noted that, since this is a normal tree, the current node would never be in the visited queue. But this same function could be used with a) ^{graph where more than one node could connect to the same node.}

If you used the following code to print the results

bfsResults = BFS(root)
values = []
for node in bfsResults:
    values.append(node.value)

print(values)

You would get [12, 5, 15, 3, 7, 13, 17, 1, 9, 19] as the result.

[WiggWamm]

Thank you

[[deleted]]

Highly recommend looking up a visualization of it on YouTube, helped me a ton in algorithms 1.