algorithm - 是否可以在 Haskell 中实现线性时间 BFS？

Question

我有一个有向图 G 作为邻接列表的列表:

newtype Graph Int = Graph [(Int, [Int])]

G有n个顶点和m条边。我正在尝试在 Haskell 中实现 BFS 算法，该算法在 O(m) 时间内运行(可能摊销)，但我能够想出的最佳解决方案在 O(m * log n) 中运行并使用 中的数据结构Data.Map模块。

我对线性解决方案的想法如下:使用 Data.Sequence 中的结构作为高效的 FIFO 队列，并按照命令式 BFS 的方式执行所有操作，但我被困在必须标记的位置访问过的节点。

我的问题是:是否可以在运行时间复杂度为 O(m) 的 Haskell(或任何其他纯函数式语言)中实现 BFS？如果不是，您可以使用什么论据来证明这种说法？

Answer 1

我假设你的问题是你不能实现一个好的队列。

看看 Data.Sequence - 它应该适用于双端队列，因为对序列末尾的操作非常快。向任一端添加一个元素是 O(1)，从任一端删除一个元素是 O(1)。

一旦拥有队列，它的性能应该与 DFS 一样好。

您可以使用 Vector Int [Int] 而不是 Map Int [Int](如果您的顶点是 1 到 n)

要将节点标记为已选中，您可以使用 IntSet。

这应该得到 O(V + E)。

bfs :: V.Vector [Int] -> Int -> [Int]
bfs graph start = go IS.empty graph $ S.singleton start

go :: IS.IntSet Int -> V.Vector [Int] -> S.Sequence Int -> [Int]
go seen graph queue = 
  case S.viewL queue of
    S.EmptyL -> []
    vertex S.:< rest = vertex:(go seen' graph queue')
      where neighbors = filter (not . IS.member seen) (graph V.! vertex)
            seen' = S.insert vertex seen
            queue' = queue S.>< S.fromList neighbors

请注意，我们构建此列表的方式完全是惰性的!因此，如果您只需要 BFS 的前半部分，则不会计算其余部分。