[Haskell-cafe] Re: Functional specification of DFS

[Vimal]

> So add another argument containing all nodes seen in any path, and
> maintain that properly. You're going to need to make your DFS >
> routine
> tail-recursive.

> The problem is efficiency. I don't know if it can be done in
> linear time
> without state (and something like arrays with O(1) access).
> Quadratic
> time (in the number of nodes) is fairly straightforward. But your
> professor did not ask for an efficient algorithm. --PR

This was what I had in mind. But, strictly speaking, when you have
three vertices like this:

G(V = {1, 2, 3}, E = {(1, 2), (2, 3)})

And you call DFS(G, 2), and say you have visited 1 first (from 2),
when you call DFS(G, 3), the visited list should contain {1, 2}, which
is not possible.

However, I had this idea:
At each level, you have atmost degree (root) choices.
So, if we have choices = [v1, v2, ..., vk], you do something similar
to a foldr, and return the spanning tree. This return value will
contain a list of visited vertices, and so, merge it with the current
list of visited vertices.

The code link is:
http://j.vimal.googlepages.com/dfs.hs

Now, I face some problem which i think is due to Lazy evaluation.
I tried adding strictness in as many meaningful places as possible,
but it doesnt work :(

I have sat with the code for a long time, and yet I am not able to
come up with a convincing reason as to why it doesnt work. For
somegraphs, it even hangs and gives a stack overflow exception!

Any help appreciated. Thanks,
Vimal