CODEWITHSUNDEEP
haskelldepth-first-search
Coding District
Coding District

Reputation: 11931

DFS implementation in Haskell

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?

Upvotes: 7

Views: 12967

Answers (2)

theluckyemil
theluckyemil

Reputation: 693

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

Upvotes: 3

Satvik
Satvik

Reputation: 11208

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.

Upvotes: 3

Related Questions