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.