haskell - 在 Haskell 中寻找穿过 DFS 森林的最长路径

Question

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

如果它有帮助(很抱歉我不能很好地打印这个，showForest显然只打印字符串)，这是dfs的输出我的图表上的命令:

[节点{rootLabel = 87，subForest = [节点{rootLabel = 82，subForest = [节点{rootLabel = 70，subForest = []]}，节点{rootLabel = 83，subForest = [节点{rootLabel = 66、subForest = [节点{rootLabel = 72，subForest = [节点{rootLabel = 88，subForest = []}]}]}，节点{rootLabel = 79，subForest = [节点{rootLabel = 69，subForest = [节点{ rootLabel = 85，subForest = []}，节点{rootLabel = 84，subForest = [节点{rootLabel = 86，subForest = []}，节点{rootLabel = 73，subForest = [节点{rootLabel = 81，subForest = [] }]}]}]}]}]}，节点{rootLabel = 89，subForest = []}]}]}]

我发现了一些不同的函数来查找树中的最长路径，例如 answer ，但它们仅适用于Tree，不适用于Forest，而且我不确定是否可以在两者之间进行转换。

谢谢!

Answer 1

正如 Shersh 在他们的答案中解释的那样，深度优先搜索不足以解决您的问题(如果是，您可以使用您链接到的答案中的 generalFold ，例如，重建森林中每棵树的最长路径)。一种替代方案是从 Data.Graph 切换到 fgl，它提供了多种图形算法，包括广度优先搜索。请注意The Haddock documentation FGL 的内容相当简洁，因此您还需要查阅 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 等内容进行一些处理。 ，但从根本上来说并不会变得更加困难。