在Haskell中是否可能实现线性时间BFS算法？

Question

在Haskell中是否可能实现线性时间BFS算法？

6

我有一个有向图G，以邻接列表的形式给出：

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

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

我的线性解决方案如下：使用Data.Sequence结构作为高效的FIFO队列，并像命令式BFS一样做所有事情，但是我卡在了必须将节点标记为已访问的地方。

我的问题是：是否可能在Haskell（或任何其他纯函数语言）中实现运行时间为O(m)的BFS？如果不行，你可以用什么论据证明这种说法？

- KCH

你是在询问是否可能实现这样的算法，还是具体地在问如何在Haskell中实现它？ - Scott Hunter

@ScottHunter：我在考虑任何纯函数式语言（我编辑了我的问题） - KCH

你的问题是实现一个 O(1) 队列吗？ - alternative

懒惰的BFS队列适用于结构化树是简单易行的（另请参阅此答案，其中包含循环检测）。 - Will Ness

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- alternative · Accepted Answer

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

请看Data.Sequence - 双端队列应该很好地解决问题，因为在序列末尾的操作非常快。在任何一端添加元素是O(1)，从任何一端删除元素也是O(1)。

一旦有了队列，它应该像DFS一样运行良好。

如果你的节点是从1到n的整数，则可以使用Vector Int [Int]而不是Map Int [Int]。

要标记已检查的节点，可以使用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的前半部分，它将不会计算剩余部分。