Major error is in the line of code: `| otherwise =  dfs&#39; g y ( v : vis )`<div><br></div><div>You need something closer to:</div><div>   let vsx = dfs&#39; g x (x : vis) in</div><div>   dfs&#39; g v vsx</div><div><br></div>
<div><div>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&#39;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&#39;` - a to-visit list and a visited list.</div>
</div><div><br></div><div>This fixes a few minor errors (you did not define y, and you added `v` to the visitors list).</div><div><br></div><div>Also, fix dfsSearch:</div><div>  dfsSearch g v = reverse $ dfs&#39; g v [v]</div>
<div><br></div><div>That is, add the node you&#39;re starting with to those you&#39;ve already visited, and since you&#39;re adding to the front of the list the element visited last, you may wish to fix that. </div><div><br>
</div><div>Order in this case is [0,4,3,2,1] due to the order from buildGraph.</div><div><br></div><div><br><div class="gmail_quote">On Tue, Nov 8, 2011 at 1:04 PM, mukesh tiwari <span dir="ltr">&lt;<a href="mailto:mukeshtiwari.iiitm@gmail.com">mukeshtiwari.iiitm@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Hello all <div>I am trying to implement depth search in Haskell.  My issue here is kind of backtracking.  Haskell code for depth first search </div>
<div><br></div><div><div>import Data.List</div><div>import Data.Array</div>
<div>import Control.Monad</div><div><br></div><div><br></div><div>type Node = Int </div><div>type Graph = Array Int [  Node  ]  </div><div><br></div><div>dfs&#39; ::  Graph -&gt; Node -&gt; [ Node ] -&gt; [ Node ] </div>
<div>
dfs&#39; g v vis = dfsfun lst where </div><div><span style="white-space:pre-wrap">        </span>lst = g ! v </div><div><span style="white-space:pre-wrap">        </span>dfsfun [] = vis </div><div><span style="white-space:pre-wrap">        </span>dfsfun ( x : xs ) </div>

<div><span style="white-space:pre-wrap">        </span>  | elem x vis = dfsfun xs </div><div><span style="white-space:pre-wrap">        </span>  | otherwise =  dfs&#39; g y ( v : vis ) </div><div><br>
</div><div>--set the flag true if the graph is direct otherwise false </div><div>buildGraph :: ( Int , Int ) -&gt; [ ( Node , Node ) ] -&gt; Bool -&gt;  Graph </div><div>buildGraph bnds xs f </div><div><span style="white-space:pre-wrap">        </span> | f =  accumArray ( flip (:) ) []  bnds xs  --direct graph a-&gt;b</div>

<div><span style="white-space:pre-wrap">        </span> | otherwise = accumArray ( flip (:) ) []  bnds xss where   --indirect a -&gt; b and b -&gt; a </div><div><span style="white-space:pre-wrap">                </span>xss =  foldr ( \ ( x , y ) b -&gt; ( y , x ) : b ) xs xs    </div>

<div><br></div><div>dfsSearch :: Graph -&gt; Int -&gt; [ Node ] </div><div>dfsSearch g v = dfs&#39; g v [] </div><div><br></div><div>Lets create a indirect graph </div></div><div><div>ghci&gt;let g = buildGraph  ( 0 , 5 ) [ ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) ] False</div>

<div>ghci&gt;g</div><div>array (0,5) [(0,[4,3,2,1]),(1,[0]),(2,[0]),(3,[0]),(4,[0]),(5,[])]</div></div><div><br></div><div><div>ghci&gt;dfsSearch g 0</div><div>[0]</div></div><div>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 </div>

<div> 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&#39; 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 . </div>

<div><br></div><div>Regards </div><span class="HOEnZb"><font color="#888888"><div>Mukesh Tiwari</div><div><br></div>
</font></span><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>