3
$\begingroup$

Given a tree $T$ and a sequence of nodes $S$, with the only constraint on $S$ being that it's done through some type of recursion - that is, a node can only appear in $S$ if all of its ancestors have already appeared, what's a good algorithm to determine if $S$ is a breadth first visit, a depth first visit, or neither?

A brute force approach is to compute every breadth first and depth first sequences and see if any is identical to $S$. Is there a better approach?

What if we don't want a yes or no answer, but a measure of distance. E.g. $breadth < S < R < U < depth$; what's a good algorithm to determine distance? (A brute force approach for this is just $max(length(longest{\_}common{\_}subsequence(S, breadth))/length(breadth))$ over every BFS - again, is there a better way to do this?)

$\endgroup$
1
$\begingroup$

Recall that both BFS and DFS are worklist algorithms. This means they maintain a "worklist" of vertices that need to be visited, but haven't been yet. You can think of the worklist as a list or set of "stuff that needs to be done", where here the kind of tasks that need to be done are of the form "visit vertex $v$". When DFS or BFS visits a vertex $v$, we find all its neighbors, and add each one that has not yet been visited to the worklist (if it is not already present in the worklist).

The only difference between DFS and BFS is in how they implement the worklist. DFS implements the worklist as a stack. BFS implements the worklist as a queue.

So, here is how you can test whether your sequence was obtained by DFS, by BFS, or by something else. Replay the sequence of visited nodes. Keep a worklist, just like DFS/BFS would, but use a set data structure, and add a timestamp to each item in the worklist recording when it first entered the worklist. At each step, when you visit a node $v$, check that $v$ is in the worklist, and check its timestamp. If its timestamp is the earliest of all items in the worklist, this is consistent with removal from a queue (i.e., BFS); if it is the latest of all items in the worklist, it is consistent with a stack (i.e., DFS); otherwise, it is neither. Then, add to the worklist each neighbor of $v$ that has not yet been visited and that isn't already in the worklist, using the same timestamp for all of them (since they all entered the worklist on the same step of the sequence).

Iterate through the entire sequence like this. If every step is consistent with DFS (i.e., consistently stack-like), then this sequence could have been generated by some DFS traversal. If every step is consistent with BFS (i.e., consistently queue-like), then this sequence could have been generated by some BFS traversal. If neither of these are true, then you know that this was generated by neither DFS nor BFS.

You can make this algorithm very efficient: at most a logarithmic slowdown compared to a DFS/BFS itself (and maybe even faster is possible).

$\endgroup$
0
$\begingroup$

If $S = a_1,\dots,a_n$, count the number of indices $i$ such that $a_i$ is the parent of $a_{i+1}$. Depth first maximizes this number. Breadth first minimizes it.

(See comments that this is not correct: these are not unique maximums and minimums; there are nonDFS and nonBFS that also maximize or minimize)

$\endgroup$
  • $\begingroup$ S can visit a node several times - it's not constrained to visit each node only once. $\endgroup$ – SRobertJames Oct 27 '13 at 11:25
  • $\begingroup$ Well, first remove the duplicates then. Or would that take too long? $\endgroup$ – Karolis Juodelė Oct 27 '13 at 11:36
  • $\begingroup$ That raises a key point which I totally missed - remove the first duplicates: Is the question insufficiently specified? If I removed the last duplicates, your algorithm would give a different answer. What metric will be independent of which ones I remove? (Extreme example: A regular BFS followed by a regular DFS; this should be 0.5 breadth / 0.5 depth) Perhaps your metric divided by something - but I'm not sure by what. $\endgroup$ – SRobertJames Oct 27 '13 at 13:02
  • $\begingroup$ I was assuming that BFS followed by DFS would be 100% BFS. If you want 50%, you can multiply my metric by $\frac{|T|}{|S|}$ (I assume $|S| \geq |T|$). $\endgroup$ – Karolis Juodelė Oct 27 '13 at 13:16
  • $\begingroup$ I don't believe this can detect BFS. There are other visits which also minimize this number which aren't BFS. (Imagine leapfrogging back and forth - visit A, then B, then child of A, then C, then grandchild of A, then child of B, etc.). In other words: DFS maximizes and BFS minimizes, but it doesn't appear to be unique minimum. $\endgroup$ – SRobertJames Oct 27 '13 at 13:24

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.