2
$\begingroup$

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: Two DFSes of a simple graph.

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".)

|cite|improve this question
$\endgroup$
  • $\begingroup$ Do you imply a directed acyclic graph? "Intuitively, DFS with (more) forward edges is 'better'/'more useful' than one with (more) cross edges". Although I would agree intuitively, can you actually explain why? $\endgroup$ – John L. Nov 12 '18 at 23:46
  • $\begingroup$ "Do you imply a directed acyclic graph?" - No, as the question says, "a graph", which is hopefully good enough rendition of "an arbitrary graph" is English ;-). $\endgroup$ – pfalcon Nov 13 '18 at 4:03
  • $\begingroup$ "Although I would agree intuitively, can you actually explain why?" Well, e.g. when graph represents a CFG (control flow graph) in the program analysis. The graph on the left could represent if (a and b) then D else Cconstruct. 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:13
  • $\begingroup$ Thanks for the clarification about direct acyclic graph. I guess you mean an undirected graph even if all graphs in your question are directed acyclic graph. By the way, how far have you tried in constructing a wanted algorithm? $\endgroup$ – John L. Nov 13 '18 at 7:30
  • $\begingroup$ On your explanation about the advantage of graph (b), you mentioned if (a and b) then D else C. However, a and b are symmetric in that snippet while A and B in graph (a) are not. $\endgroup$ – John L. Nov 13 '18 at 7:34

Your Answer

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

Browse other questions tagged or ask your own question.