[Haskell] DFS与BFS

1. DFS

import Data.Ix
import Graph
import Stack 

depthFirstSearch :: Ix a => a -> Graph a a -> [a]
depthFirstSearch start g = dfs [start] []
    where 
        dfs [] vis = vis 
        dfs (c:cs) vis | elem c vis = dfs cs vis 
                       | otherwise  = dfs ((adjacent g c) ++ cs) (vis ++ [c]) 

depthFirstSearch' :: Ix a => a -> Graph a a -> [a]
depthFirstSearch' start g = reverse $ dfs [start] []
    where 
        dfs [] vis = vis 
        dfs (c:cs) vis | elem c vis = dfs cs vis 
                       | otherwise  = dfs ((adjacent g c) ++ cs) (c:vis)

depthFirstSearch'' :: Ix a => a -> Graph a a -> [a]
depthFirstSearch'' start g = reverse $ dfs (push start emptyStack) []
    where 
        dfs s vis | (stackEmpty s) = vis 
                  | elem (top s) vis = dfs (pop s) vis 
                  | otherwise = let c = top s 
                                in 
                                    dfs (foldr push (pop s) (adjacent g c))
                                        (c:vis)

2. BFS

import Data.Ix
import Graph
import Queue

breadFirstSearch :: Ix a => a -> Graph a a -> [a]
breadFirstSearch start g = reverse (bfs (enqueue start emptyQueue) [])
    where 
        bfs q vis | (queueEmpty q) = vis 
                  | elem (front q) vis = bfs (dequeue q) vis 
                  | otherwise = let c = front q
                                in
                                    bfs (foldr enqueue 
                                               (dequeue q)
                                               (adjacent g c))
                                        (c:vis)

---

参考

Algorithms: A Functional Programming Approach
Stack
Queue
Graph - 邻接表
Graph - 邻接矩阵