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):
Document 1.1
Document 1.3.1
Document 1.2.1.1.1
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
aboveDocument 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.