haskell - 寻找通过Haskell的DFS森林的最长路径

我有一张图，我试图找到最长的路径，但不确定如何去做。我使用的是 Graph 的标准Edge和Data.Graph类型，并且该图是使用buildG函数生成的。我最初的想法是使用dfs进行深度优先搜索，但这产生了一个Forest对象，我不确定该如何操作。

如果这完全有帮助(对不起，我无法漂亮地打印出来，showForest仅显示字符串)，那么这是我图上dfs命令的输出:
[Node {rootLabel = 87, subForest = [Node {rootLabel = 82, subForest = [Node {rootLabel = 70, subForest = []},Node {rootLabel = 83, subForest = [Node {rootLabel = 66, subForest = [Node {rootLabel = 72, subForest = [Node {rootLabel = 88, subForest = []}]}]},Node {rootLabel = 79, subForest = [Node {rootLabel = 69, subForest = [Node {rootLabel = 85, subForest = []},Node {rootLabel = 84, subForest = [Node {rootLabel = 86, subForest = []},Node {rootLabel = 73, subForest = [Node {rootLabel = 81, subForest = []}]}]}]}]}]},Node {rootLabel = 89, subForest = []}]}]}]
我发现了一些用于查找穿过树的最长路径的函数，例如answer，但是它们仅适用于Tree，不适用于Forest，并且我不确定是否可以在两者之间进行转换。

谢谢!

最佳答案

正如Shersh在他们的答案中所解释的那样，深度优先搜索不足以解决您的问题(如果是这样，您可以使用链接到的答案中的generalFold，例如，重建森林中每棵树的最长路径) 。一种选择是从Data.Graph切换到fgl，它提供了多种图形算法，包括广度优先搜索。请注意，FGL的The Haddock documentation非常简单，因此您还想通过package homepage查阅有用的用户指南。在下面的演示中，我将使用 bft 函数获取图的广度优先的生成树，这应该足以使您入门:

GHCi> import Data.Graph.Inductive.Graph
GHCi> import Data.Graph.Inductive.PatriciaTree
GHCi> import Data.Graph.Inductive.Query.BFS
GHCi> :{
GHCi| test :: UGr
GHCi| test = mkUGraph [1..7] [(1,3),(1,2),(2,4),(3,5),(2,6),(5,2),(5,7)]
GHCi| :}
GHCi> prettyPrint test
1:()->[((),2),((),3)]
2:()->[((),4),((),6)]
3:()->[((),5)]
4:()->[]
5:()->[((),2),((),7)]
6:()->[]
7:()->[]
GHCi> bft 1 test
[[1],[2,1],[3,1],[4,2,1],[6,2,1],[5,3,1],[7,5,3,1]]

生成树实质上是从节点到所有可到达节点的路径的列表。例如，如果您只想找到最大长度的路径之一，而不关心绘制，那么您所需要做的就是:

GHCi> import Data.Ord
GHCi> import Data.List
GHCi> maximumBy (comparing length) (bft 1 test)
[7,5,3,1]

如果您确实关心平局，那么您将需要对 groupBy 之类的东西进行些杂耍，但这从根本上讲不会更加困难。