Name of BFS variant with multiple queues with different priorities

Question

Is there a name for the following variant of BFS that operates on trees with non-root starting point?:

• Instead of a single queue that all neighbor nodes are added to when processing a node, two queues are used ($Q_A$ and $Q_B$).
• Children nodes are added to $Q_A$, and parent nodes are added to $Q_B$.
• When selecting the next node to process, $Q_A$ is drawn from, and only when $Q_A$ is empty is $Q_B$ drawn from.

One application for this (and the one that made me think of this) is for ranking "close" documents in a folder hierarchy (based on the leaf-node discovery order of the algorithm). For example in the following hierarchy:

- Root Folder
  - Folder 1
    - Document 1.1
    - Folder 1.2
      - Folder 1.2.1
        - Folder 1.2.1.1
          - Document 1.2.1.1.1
    - Folder 1.3
      - Document 1.3.1
  - Folder 2
    - Document 2.1

If we start our search at Document 1.1 we would like to see the following ranking (which the algorithm produces):

1. Document 1.1
2. Document 1.3.1
3. Document 1.2.1.1.1
4. Document 2.1

Document 1.2.1.1.1 should appear higher than Document 2.1 since there is a closer common ancestor (Folder 1), even though the former is technically further away (distance of 4 vs. 5).

Some other things I considered that don't actually work:

• BFS using a single queue but always enqueuing the parent last. This doesn't work as it's still regular BFS and ranks based on shortest path.
• DFS, and always pushing the parent onto the stack first so it's discovered last. This could rank Document 1.2.1.1.1 above Document 1.3.1 depending on the order children are enqueued.

This seems like a pretty standard algorithm, but I couldn't find anything when I searched for it, so I was hoping someone might recognize it and know what it's called.

Answer 1

I don't think this particular implementation has a name, but there is a slightly different implementation that achieve the same goal and has a name: BFS 0-1.

Let me briefly describe the algorithm, and then let's solve your problem using this algorithm. For more complete description use previous link or Google about, it has a name.

Suppose you have a general graph (a tree will also work) where each edge has a weight, but the weight can only be 0 or 1. You are given a source node and should find minimal distance to every other node in the graph. This can be easily solved with Dijkstra's algorithm but complexity worsens. Instead of using Dijkstra, let's use BFS, with a deque (in the place of the queue). When we are traversing an edge with weight 0 we add this node to the beginning of the deque, otherwise you add it at the end.

Without going too much into the details of BFS 0-1 I'll apply it to your problem. Suppose that every time you are visiting an unvisited parent you add it to the end of the deque, and when you are visiting an unvisited child you add it to the front of the deque. The order in which you will visit the nodes in your file system will be the one desired. Notice now, that we are treating edges going to a parent as if they have weight 1, and edges going to children as if they have edge 0 (graph is obviously directed, since each edge has different weight when direction changes). The distance to each node from the source will be the distance to the closest common ancestor in the initial tree.

---

This is not exactly the same algorithm you were proposing, but notice that using the idea of two queues, is the same as having the deque and inserting from the beginning or from the end, so we can say both algorithms are basically equivalent. It can be naturally extended following your idea to support graphs were edges has weight such that they are numbers between $0$ and $k - 1$, using $k$ queues, however it is more tricky and out of the scope of this question.