Re: Depth Fist Search and Breadth First Search and using array
- From: Logan Shaw <lshaw-usenet@xxxxxxxxxxxxx>
- Date: Sat, 29 Sep 2007 21:11:48 -0500
Summercool wrote:
I just wonder if for DFS (Depth Fist Search), we don't really need an
array to act as a Stack (LIFO), but we can just use recursion.
Yes, you can do that. Some people avoid recursion because it's slow
(it doesn't have to be) or because they are using a language/environment
with a fixed, limited stack size. But recursion does not have to suffer
from either of those problems.
Now, however, if our program is to spider the web, or to go
down the game tree, and we set the levelMax to 10, then the stack
overflow problem is really not there, as the deepest call stack level
is 10.
That's true. Limiting the depth is not always appropriate for every
problem, but it could be for some problems.
Is it true that for BFS (Breadth First Search), we always have to use
an array as a Queue (FIFO)?
First, a queue doesn't have to be implemented with an array. But that's
a side issue.
Second, you can certainly do breadth first search without a queue. The
most obvious method that springs to mind for me is iterative deepening,
where basically you repeatedly do recursive traversals but pass a depth
parameter to each traversal. Then you only look at items that are at
the depth you're considering for that one traversal.
So, for example:
void print_at_depth(node* n, int depth) {
if (n == NULL) return;
if (depth == 0) {
print n->data;
} else {
print_at_depth(n->left, depth - 1);
print_at_depth(n->right, depth - 1);
}
}
You'd loop something like this:
for (int depth = 0; whatever(); depth++) {
print_at_depth(root, depth);
}
This technique seems a bit wasteful, but when you analyze it, its asymptotic
running time behavior is not bad. And it certainly saves on temporary storage
compared to using a queue.
Using an array seems a bit like a "global
variable".
It is less elegant than a recursive traversal, but it isn't bad design
to use a queue. And you certainly don't have to use a global variable.
If you do it iteratively, you never need to change scopes, so you can
use a local variable if you want.
- Logan
.
- References:
- Depth Fist Search and Breadth First Search and using array
- From: Summercool
- Depth Fist Search and Breadth First Search and using array
- Prev by Date: Re: whoever you hire, make sure it isn't a college graduate
- Next by Date: Re: time complexity
- Previous by thread: Depth Fist Search and Breadth First Search and using array
- Next by thread: whoever you hire, make sure it isn't a college graduate
- Index(es):
Relevant Pages
|
