haskell - 函数拓扑排序

Question

在拓扑排序算法中，我们执行 DFS 并将遇到的节点推送到链表上。我能想到的实现这一功能的唯一方法是将列表作为参数传递到调用中，这是丑陋且非常低效的(即，它显示在大 O 中，因为复制列表的时间复杂度为 O(n)。在 Haskell 中如何以惯用的方式做到这一点？

Answer 1

fgl paper讨论这个确切的问题，作为如何以函数式风格进行图算法的第一个示例:

dfs :: [Node] -> Graph a b -> [Node]
dfs []     g        = []
dfs (v:vs) (c &v g) = v:dfs (suc c++vs) g
dfs (v:vs) g        = dfs vs g

[Editor's note: the notation c &v g is introduced earlier in the paper as a kind of "pattern match on graphs": c &v g matches graphs containing the vertex v, binding c to a context giving edges in and out of the vertex and g to the graph with that node and all its edges deleted. In the Haskell library, this is realized by the function match.]

The algorithm works as follows. If there are no nodes left to be visited (first case), dfs stops without returning any nodes. In contrast, if there are still nodes that must be visited, dfs tries to locate the context of the first of these nodes (v) in the argument graph. If this is possible (second equation), which is the case whenever v is contained in the argument graph, v is the next node on the resulting node list, and the search continues on the remaining graph g with the successors of v to be visited before the remaining list of nodes vs. The fact that the successors are put in front of all other nodes causes dfs to favor searching in the depth and not in the breadth. Finally, if v cannot be matched (last line), dfs continues the search with the remaining list of nodes vs. Note that the last case can only occur if v is not contained in the graph because otherwise the pattern in the second equation would have matched.

由于复制粘贴功能无法正常工作，我不得不转录此文本；几乎可以肯定，任何拼写错误都是我造成的，而不是马丁·厄维格的。

正如您所建议的，剩余要访问的节点列表作为参数传入。然而，你认为这效率低下的说法对我来说似乎偏离了目标；构建新列表 suc c++vs 的成本是 O(length (suc c)) - 但随后您必须至少访问所有这些节点一次无论如何都要完成深度优先搜索，因此渐近成本是不可避免的。

上面链接的全文花了相当多的时间讨论渐进和效率，并且(在我看来)也很有启发性，所以我鼓励您阅读它。