scala - Tarjan 强连通分量算法的功能实现

Question

我继续并 implemented textbook version of Tarjan's SCC algorithm在斯卡拉。然而，我不喜欢这个代码——它是非常命令式/程序性的，有很多变异状态和簿记索引。该算法是否有更“功能”的版本？我相信命令式版本的算法隐藏了算法背后的核心思想，与函数式版本不同。我发现someone else encountering the same problem使用这个特定的算法，但我无法将他的 Clojure 代码翻译成 idomatic Sc​​ala。

注意:如果有人想尝试，我有一个很好的设置，可以生成随机图和 tests your SCC algorithm vs running Floyd-Warshall

Answer 1

参见Lazy Depth-First Search and Linear Graph Algorithms in Haskell作者:大卫·金和约翰·朗伯里。它以函数式风格描述了许多图算法，包括 SCC。