patternMinor
Algorithm to determine if recursion was breadth first or depth first
Viewed 0 times
depthrecursionbreadthalgorithmfirstdeterminewas
Problem
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?)
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?)
Solution
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).
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).
Context
StackExchange Computer Science Q#16459, answer score: 2
Revisions (0)
No revisions yet.