如何在Haskell中实现图的遍历算法

在Haskell中实现图的遍历算法通常使用递归函数来实现深度优先搜索（DFS）或广度优先搜索（BFS）算法。以下是一个简单的示例，用于实现图的DFS算法：

import Data.Map (Map)
import qualified Data.Map as Map

type Graph a = Map a [a]

dfs :: Ord a => Graph a -> a -> [a]
dfs graph start = dfs' [start] []
  where
    dfs' [] visited = reverse visited
    dfs' (node:rest) visited
      | node `elem` visited = dfs' rest visited
      | otherwise = dfs' (neighbors ++ rest) (node:visited)
      where neighbors = case Map.lookup node graph of
                          Just ns -> ns
                          Nothing -> []

-- 示例用法
exampleGraph :: Graph Char
exampleGraph = Map.fromList
  [('A', ['B', 'C']),
   ('B', ['A', 'D', 'E']),
   ('C', ['A', 'F']),
   ('D', ['B']),
   ('E', ['B', 'F']),
   ('F', ['C', 'E'])]

main :: IO ()
main = do
  let result = dfs exampleGraph 'A'
  putStrLn $ "DFS traversal: " ++ show result

在上面的示例中，我们定义了一个Graph类型，表示邻接表形式的图。然后实现了一个dfs函数，该函数使用递归方式进行深度优先搜索。最后，我们定义了一个示例图exampleGraph，并在main函数中展示了如何使用dfs函数进行图的遍历。

如果需要实现广度优先搜索算法，可以使用队列来实现。整体思路和DFS类似，只是使用队列来维护访问顺序。