Is the first width or width search the first crawl without using a queue?

Question

As I remember and tested, the usual way of traversing a tree or traversing the width of a web page (BFS) is to use a queue. Is there a way to implement it without using a queue?

Answer 1

You really should use a queue as it is easier to implement. In addition, the queue allows multiple machines to work together (one queue node, while other sites pop up from the queue to go through).

The only other way that I see for this is to use recursion (much more complicated and uses only negligible or larger or smaller memory).

Answer 2

I know this question is old now, but I just wanted to answer. You can do this with arrays, linked lists (or any other linear container) and without recursion. Save the two containers, old and new , and replace old with new when you go through all the elements in old . Very similar to a queued implementation.

In Python, it will look like this:

 def breadth_first(root): if not root: return old = [] new = [] old.append(root) while old: for n in old: process(n) # Do something if n.left: new.append(n.left) if n.right: new.append(n.right) old = new new = [] 

The complexity of the execution will be the same as the implementation of the queue, O (n).

Answer 3

With recursion. But the queue is on the stack ...

Answer 4

if you want to arrange, use the queue. the queue maintains the insertion order. or you can use an implementation of a list of, say, two lists of arrays to interleave. But basically, the list also keeps order.

if you do not care about the order, you can use any installed implementations. sets do not preserve this order.

For example, in a BFS implementation, if you do not like the ordering of nodes, you can use two sets, old and new, to alternate, rather than in a queue.