Major error is in the line of code: `| otherwise = dfs' g y ( v : vis )`
You need something closer to:
let vsx = dfs' g x (x : vis) in
dfs' g v vsx
That is, first visit everything you can reach from x, then backtrack to add
anything else you can reach from v. This implementation will forget which
nodes you've already visited from v, though that might not be a big issue.
If you want to fix it, separate the `list = g ! v` into the caller, rather
than the callee, such that there are two lists at `dfs'` - a to-visit list
and a visited list.
This fixes a few minor errors (you did not define y, and you added `v` to
the visitors list).
Also, fix dfsSearch:
dfsSearch g v = reverse $ dfs' g v [v]
That is, add the node you're starting with to those you've already visited,
and since you're adding to the front of the list the element visited last,
you may wish to fix that.
Order in this case is [0,4,3,2,1] due to the order from buildGraph.
On Tue, Nov 8, 2011 at 1:04 PM, mukesh tiwari
Hello all I am trying to implement depth search in Haskell. My issue here is kind of backtracking. Haskell code for depth first search
import Data.List import Data.Array import Control.Monad
type Node = Int type Graph = Array Int [ Node ]
dfs' :: Graph -> Node -> [ Node ] -> [ Node ] dfs' g v vis = dfsfun lst where lst = g ! v dfsfun [] = vis dfsfun ( x : xs ) | elem x vis = dfsfun xs | otherwise = dfs' g y ( v : vis )
--set the flag true if the graph is direct otherwise false buildGraph :: ( Int , Int ) -> [ ( Node , Node ) ] -> Bool -> Graph buildGraph bnds xs f | f = accumArray ( flip (:) ) [] bnds xs --direct graph a->b | otherwise = accumArray ( flip (:) ) [] bnds xss where --indirect a -> b and b -> a xss = foldr ( \ ( x , y ) b -> ( y , x ) : b ) xs xs
dfsSearch :: Graph -> Int -> [ Node ] dfsSearch g v = dfs' g v []
Lets create a indirect graph ghci>let g = buildGraph ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) ] False ghci>g array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])]
ghci>dfsSearch g 0 [0] Here I am getting only 0 but it should return [ 0 , 1 , 2 , 3 , 4 ] . What is happening here when i am passing 0 as root node to function , at first level i get lst = [ 4 , 3, 2, 1 ] . First element of this list is 4 so 0 is added to vis list and now 4 is passed to dfs' as parent. When it goes down , we get lst = [0] and since 0 is member of vis list so it returns the vis as result . When we write dfs in c/c++ then it returns to calling function and again loops through remaining element which i am not able visualize in Haskell. Could some one please help me how to solve this issue .
Regards Mukesh Tiwari
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe