# 99 questions/Solutions/87

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

Jagbolanos (Talk | contribs) (Depth First Search in a graph) |
Jagbolanos (Talk | contribs) |
||

Line 1: | Line 1: | ||

− | + | <haskell> | |

− | + | type Node = Int | |

− | + | type Edge = (Node,Node) | |

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

− | + | ||

+ | 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 (_,_) [] = [] | |

+ | 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 18: | ||

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: | ||

− | + | <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