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