[Haskell-cafe] Depth first search
mukesh tiwari
mukeshtiwari.iiitm at gmail.com
Tue Nov 8 22:04:33 CET 2011
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111109/6274508e/attachment.htm>
More information about the Haskell-Cafe
mailing list