I've been banging my head over the wall for a few hours as I can't figure out how to write DFS in Haskell..
My graph is implemented as an adjacency list where the keys (or node name of the graph) are list indices:
0 -> 1
1 -> 0, 2
2 -> 1
As a Haskell list: [[1],[0,2],[1]]
Here's my code so far for DFS:
dfs graph visited node = helper graph visited (graph !! node) node
where helper _ _ visited [] _ = visited
helper graph visited (x:xs) currNode
| elem x visited = helper graph visited xs currNode
| otherwise = dfs graph (currNode:visited) x
I understand that the problem is that it doesn't backtrack and try another adjacent node once it reaches one end of the graph. I've been trying to modify the otherwise section of the guard in an attempt to fix it but can't seem to come up with something that works. What can I do to fix this?
2 Answers 2
What you are trying to do is still not very clear to me. I have written something similar to yours although it has the same problem that !! is not O(1), but it is still dfs.
mydfs graph visited [] = reverse visited
mydfs graph visited (x:xs) | elem x visited = mydfs graph visited xs
| otherwise = mydfs graph (x:visited) ((graph !! x) ++ xs)
The idea for dfs to backtrack is to keep a list of tobevisited and just take out the first entry from it and visit it and whenever you find an entry that is not visited push its adjacent vertices on top of the tobevisited list.
You can use arrays or vectors for adjacency list to avoid O(n) lookup, but it is better to use graph libraries for what you are trying to do.
Shortest I could come up with
dfs current visited =
foldl (\visited next -> if elem next visited then visited else dfs next visited)
(visited ++ [current]) (graph !! current)
Compare with python:
def dfs(v, visited):
visited.append(v)
for u in graph[v]:
if u not in visited:
visited = dfs(u, visited)
return visited
!!is O(n) in worst case, so the complexity of your dfs will be much larger.