Difference between revisions of "99 questions/Solutions/87"
From HaskellWiki
< 99 questions  Solutions
Jagbolanos (talk  contribs) (Depth First Search in a graph) 
Jagbolanos (talk  contribs) 

Line 1:  Line 1:  
−  type Node = Int 

+  <haskell> 

−  +  type Node = Int 

−  +  type Edge = (Node,Node) 

−  +  type Graph = ([Node],[Edge]) 

−  +  
+  depthfirst :: Graph > Node > [Node] 

+  depthfirst (v,e) n 

 [xx<v,x==n] == [] = [] 
 [xx<v,x==n] == [] = [] 

 otherwise = dfrecursive (v,e) [n] 
 otherwise = dfrecursive (v,e) [n] 

−  dfrecursive :: Graph > [Node] > [Node] 

+  
−  +  dfrecursive :: Graph > [Node] > [Node] 

−  +  dfrecursive ([],_) _ = [] 

−  +  dfrecursive (_,_) [] = [] 

+  dfrecursive (v,e) (top:stack) 

 [xx<v,x==top] == [] = dfrecursive (newv, e) stack 
 [xx<v,x==top] == [] = dfrecursive (newv, e) stack 

 otherwise = top : dfrecursive (newv, e) (adjacent ++ stack) 
 otherwise = top : dfrecursive (newv, e) (adjacent ++ stack) 

Line 15:  Line 15:  
adjacent = [x  (x,y)<e,y==top] ++ [x  (y,x)<e,y==top] 
adjacent = [x  (x,y)<e,y==top] ++ [x  (y,x)<e,y==top] 

newv = [xx<v,x/=top] 
newv = [xx<v,x/=top] 

−  
+  </haskell> 

Call it: 
Call it: 

⚫  
+  <haskell> 

⚫  
+  </haskell> 
Revision as of 23:26, 5 March 2011
type Node = Int
type Edge = (Node,Node)
type Graph = ([Node],[Edge])
depthfirst :: Graph > Node > [Node]
depthfirst (v,e) n
 [xx<v,x==n] == [] = []
 otherwise = dfrecursive (v,e) [n]
dfrecursive :: Graph > [Node] > [Node]
dfrecursive ([],_) _ = []
dfrecursive (_,_) [] = []
dfrecursive (v,e) (top:stack)
 [xx<v,x==top] == [] = dfrecursive (newv, e) stack
 otherwise = top : dfrecursive (newv, e) (adjacent ++ stack)
where
adjacent = [x  (x,y)<e,y==top] ++ [x  (y,x)<e,y==top]
newv = [xx<v,x/=top]
Call it:
depthfirst ([1,2,3,4,5],[(1,2),(2,3),(1,4),(3,4),(5,2),(5,4)]) 1