0

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.

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!

| improve this answer | |
  • You say: Add to priority queue with level of node + 1. But what does it mean? what is + 1? I don't understand you – porton Oct 11 '17 at 13:08
  • Particularly what is "level of node"? – porton Oct 11 '17 at 13:13
  • 1
    @porton Think of it as an endless tree, with the root being the node start point. Every step away from start node adds one to the level. The decision to grab a particular node in priority queue is based on the current level. Adding 1 to current level is a means to keep tabs on that as you traverse your graph. And since it is a graph, you'll likely need to remember which nodes have been visited already. – Neil Oct 12 '17 at 8:45
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.

| improve this answer | |
  • If all edges are preferred, your algorithm always gives depth-first search. I want to implement both depth-first and breadth-first. So your answer does not suite me. It seems that the other answer (with priority queue) suits better – porton Oct 11 '17 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.