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 188.8.131.52 - Document 184.108.40.206.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 220.127.116.11.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.3.1depending 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.