Difference between revisions of "99 questions/Solutions/87"
< 99 questions | Solutions
Jump to navigation
Jump to search
Jagbolanos (talk | contribs) (Depth First Search in a graph) |
Jagbolanos (talk | contribs) |
||
Line 1: | Line 1: | ||
+ | <haskell> |
||
− | type Node = Int |
||
− | + | type Node = Int |
|
− | + | type Edge = (Node,Node) |
|
− | + | type Graph = ([Node],[Edge]) |
|
+ | |||
⚫ | |||
⚫ | |||
⚫ | |||
| [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> |
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