Personal tools

99 questions/Solutions/87

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
(Depth First Search in a graph)
 
 
Line 1: Line 1:
type Node = Int
+
<haskell>
type Edge = (Node,Node)
+
type Node = Int
type Graph = ([Node],[Edge])
+
type Edge = (Node,Node)
depthfirst :: Graph -> Node -> [Node]
+
type Graph = ([Node],[Edge])
depthfirst (v,e) n
+
  +
depthfirst :: Graph -> Node -> [Node]
  +
depthfirst (v,e) n
 
| [x|x<-v,x==n] == [] = []
 
| [x|x<-v,x==n] == [] = []
 
| otherwise = dfrecursive (v,e) [n]
 
| otherwise = dfrecursive (v,e) [n]
dfrecursive :: Graph -> [Node] -> [Node]
+
dfrecursive ([],_) _ = []
+
dfrecursive :: Graph -> [Node] -> [Node]
dfrecursive (_,_) [] = []
+
dfrecursive ([],_) _ = []
dfrecursive (v,e) (top:stack)
+
dfrecursive (_,_) [] = []
  +
dfrecursive (v,e) (top:stack)
 
| [x|x<-v,x==top] == [] = dfrecursive (newv, e) stack
 
| [x|x<-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 = [x|x<-v,x/=top]
 
newv = [x|x<-v,x/=top]
+
</haskell>
   
 
Call it:
 
Call it:
   
depthfirst ([1,2,3,4,5],[(1,2),(2,3),(1,4),(3,4),(5,2),(5,4)]) 1
+
<haskell>
  +
depthfirst ([1,2,3,4,5],[(1,2),(2,3),(1,4),(3,4),(5,2),(5,4)]) 1
  +
</haskell>

Latest 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
    | [x|x<-v,x==n] == [] = []
    | otherwise = dfrecursive (v,e) [n]
 
dfrecursive :: Graph -> [Node] -> [Node]
dfrecursive ([],_) _ = []
dfrecursive (_,_) [] = []
dfrecursive (v,e) (top:stack)
    | [x|x<-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 = [x|x<-v,x/=top]

Call it:

depthfirst ([1,2,3,4,5],[(1,2),(2,3),(1,4),(3,4),(5,2),(5,4)]) 1