Breadth-first traversal with some edges preferred

Question

Let we have a (finite or infinite) directed graph and a start vertex. For each vertex we have the set of edges from this vertex totally ordered to specify the traversal order. Let we also have a set P of "preferred" edges.

I want to traverse this graph. This could be accomplished as either depth-first or breadth-first algorithm (respecting the order of the edges).

But I want to traverse through preferred edges before all other edges.

For depth-first traversal there is no trouble: Just re-order every set of edges from each vertex in such a way that the preferred edges come first.

But for breadth-first traversal we have a problem: Even if we reorder to put preferred edges first, breadth-first traversal may visit preferred edges later than non-preferred ones, because "deeper" edges are traversed always later than the current level.

Please help to formalize the idea of "breadth-first traversal but with preferred edges taking precedence". How to describe the algorithm for this kind of traversal? If there are several distinct formalizations of my idea, please describe all simple-enough formalizations. If there are several "isomorphic" ways to describe the same order, I want to know all (simple enough) ways.

Answer 1

A priority queue here would likely serve you best. A priority queue is nothing more than a queue that orders based on a criteria.

Algorithm

You start by adding the start node to the list associated with level 0.

The algorithm is as follows:

Pop a node.  
For each edge in node
    Add to priority queue with level of node + 1

Depth first

The key here is specifying the criteria for your order. Depth first simply orders by level (descending), so that you will always pop the "deepest" node first.

Simple breadth first

For simple breadth first, it is the opposite. Order by level ascending, so the "shallowest" nodes are picked first.

Slightly less simple breadth first

So how would you then go about picking preferenced nodes with same level first?  You simply change the criteria such that level trumps any other ordering you could have.  This guarantees that you get breadth first search.  The second ordering will have an impact, but only if level does not have a say.

Supposing you were determining a node's "score", that might be something like:

10000*level + getSecondaryPriority()

This assumes of course that your second priority never exceeds 10000, but in more formal terms, for any two nodes, whichever comes first should be regarded first by comparing its level. If the levels are equal, then only then you compare by its secondary priority. In Java that might look something like:

public int compare(Node node1, Node node2) {
    int levelDiff = node1.level - node2.level;
    return levelDiff != 0 ? levelDiff : node1.getSecondaryPriority() - node2.getSecondaryPriority();
}

Conclusion

This solution is also somewhat cleaner also for the fact that the algorithm does not differ, only the ordering of the priority queue. Priority queues are used to help chess AI determine which considerations should be weighed first (i.e. if queen is in danger, decision tree considers more heavily a decision involving moving the queen and consequently potential counter-moves by the player over other courses of action in what is undoubtedly an endless decision tree).

Hope that helps!

Answer 2

A depth-first traversal and a breadth-first traversal can both be accomplished using a queue for storage and simple loop. Initially enqueue the start vertex. Then, removing nodes from the head of the until the list is empty, for each removed node add all of its children to the list.

For breadth-first traversal, add the child nodes to the end of the queue.

For depth-first traversal, add the child nodes to the beginning of the queue (perhaps in reverse child order).

So, perhaps what you might consider is conditionally adding nodes to the beginning if the reaching edge is preferred vs. to the end if the reaching edge is not preferred.

This will mix depth-first and breadth-first, based on peferred'ness of the edges.

(see here for a comparison of BFS and DFS)

---

Additional alternatives might involve using a priority queue if you can assign, say, a numeric preference to the node going into the queue, possibly based on depth and other factors. Then you can insert the nodes to visit into a proper place in the priority queue.