It's well known that depth-first search order of a graph is (usually) not unique, and multiple orders are possible depending on the order in which successors are processed for each node. Let's consider rooted directed graphs in the following discussion.
Muchnick 1997 gives an example:
.
Intuitively, DFS with (more) forward edges is "better"/"more useful" than one with (more) cross edges. Is there a methodology/algorithm for ordering successor selection to construct such DFS spanning trees (like (b) in the example above)? (Of course, an algorithm better than generating all possible DFS trees in exponential time and then selecting "the best".)
if (a and b) then D else C
construct. The DFS tree in the middle, with forward edge, arguably "preserves" "shape" of this meaning, while one with cross edge arguably "obfuscates". $\endgroup$ – pfalcon Nov 13 '18 at 4:13if (a and b) then D else C
. However,a
andb
are symmetric in that snippet while A and B in graph (a) are not. $\endgroup$ – John L. Nov 13 '18 at 7:34