P87 - 图的深度优先遍历
Depth-first graph traversal
官方模块：
Problems.P87核心函数：depthFirst
题目描述
从指定顶点出发，以深度优先顺序返回所有可达顶点。邻居来自 Set，因此这里按升序展开，结果可复现。
实现
方法一：标准实现
1depthFirst :: G -> Vertex -> [Vertex]
2depthFirst graph start = reverse (snd (visit start (Set.empty, [])))
3 where
4 visit vertex state@(seen, order)
5 | Set.member vertex seen = state
6 | otherwise = foldl (flip visit) state'
7 (Set.toAscList (neighbors vertex graph))
8 where state' = (Set.insert vertex seen, vertex : order)
状态 (seen, order) 显式在线程中传递；先记录当前顶点，再递归邻居，就是前序 DFS。
方法二：显式栈
1depthFirstStack :: G -> Vertex -> [Vertex]
2depthFirstStack graph start = visit Set.empty [start]
3 where
4 visit _ [] = []
5 visit seen (vertex:stack)
6 | Set.member vertex seen = visit seen stack
7 | otherwise = vertex : visit seen'
8 (Set.toAscList (neighbors vertex graph) ++ stack)
9 where
10 seen' = Set.insert vertex seen
递归版本把待访问邻居放在调用栈中；这个版本将它们显式放入列表栈。邻居加入栈顶，所以仍会先深入当前分支。
方法对比
| 方法 | 待访问状态 |
|---|---|
| 递归 DFS | Haskell 调用栈 |
| 显式栈 | 普通顶点列表 |
测试
1>>> let graph = toG (Paths [[1,2,3,4,5],[2,4],[6,7]])
2>>> depthFirst graph 1
3[1,2,3,4,5]
4>>> depthFirst graph 6
5[6,7]
6>>> depthFirstStack graph 1 == depthFirst graph 1
7True
每个顶点和边至多处理常数次，时间复杂度 。