在Haskell中查找通过DFS森林的最长路径

Question

我有一张图表，我试图找到最长的路径，但我不确定如何去做。我使用Data.Graph中的标准Graph和Edge类型，并且使用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 s，而不是Forest s，我不确定是否有可能在两者之间进行转换。

谢谢！

Answer 1

正如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这样的东西，但它不会在根本上更困难。

Answer 2

我会先解释一下dfs是做什么的。正如你在评论中提到的那样，你使用buildG函数，所以我也会在我的答案中使用它。

dfs需要2个参数：图形和根节点列表。然后dfs运行深度优先搜索从列表中的每个顶点编号开始，从列表中的这些节点返回可到达顶点的Tree。例如：

1. 你有1个顶点的图形，你想找到路径从1这样您就可以列表，只有一个Tree其中root标签1和subforest是空的。
2. 您有2个顶点和1到2的边的图形，并且您希望从1中找到路径。然后，您将拥有仅有一个Tree的列表，其中根标签为1，并且subforest以2作为根标签列表。
3. 您有3个顶点和边（1,2）和（1,3）的图，并且您想从1中找到路径。然后您将拥有只有一个Tree的列表，其中根标号为1，并且子森林列表为两个相应地以2和3作为根标签的树。

所有这些例子（甚至更多）在接下来的ghci中证明会议：

λ: let g = buildG (1,1) [] 
λ: dfs g [1] 
[Node {rootLabel = 1, subForest = []}] 
λ: dfs g [2] 
*** Exception: Ix{Int}.index: Index (2) out of range ((1,1)) 
λ: let g = buildG (1,2) [(1,2)] 
λ: dfs g [1] 
[Node {rootLabel = 1, subForest = [Node {rootLabel = 2, subForest = []}]}] 
λ: dfs g [2] 
[Node {rootLabel = 2, subForest = []}] 
λ: let g = buildG (1,3) [(1,2), (1,3)] 
λ: dfs g [1] 
[Node {rootLabel = 1, subForest = [Node {rootLabel = 3, subForest = []},Node {rootLabel = 2, subForest = []}]}] 

但不幸的是，dfs不能帮助您与您的任务：找出从给定的最远的顶点一。在算法的工作方式，它只是不能解决这些问题。假设有4个顶点和边图形：

1→2,2→3,3→4,1→4

顶点具有最长路径从图1是图3（此路径具有2个边缘）。但是dfs将根据您指定的边缘顺序返回不同的结果。

λ: let g = buildG (1,4) [(1,2), (1,4), (2,3), (3,4)] 
λ: dfs g [1] 
[Node {rootLabel = 1, subForest = [Node {rootLabel = 4, subForest = []},Node {rootLabel = 2, subForest = [Node {rootLabel = 3, subForest = []}]}]}] 
λ: let g = buildG (1,4) [(1,4), (1,2), (2,3), (3,4)] 
λ: dfs g [1] 
[Node {rootLabel = 1, subForest = [Node {rootLabel = 2, subForest = [Node {rootLabel = 3, subForest = [Node {rootLabel = 4, subForest = []}]}]}]}] 

这不是特定实施的问题。这就是dfs的工作原理。一般情况下，您不能使用dfs来解决您的特定问题。另外，这个问题不能通过重新排列列表中的边来解决，因为你不知道如何重新排列它们。

你真正需要使用的是bfs算法 - 广度优先搜索。遗憾的是，它并未在Data.Graph库中实施。所以你需要从零开始执行整个算法，或者在某处找到实现（这里有一些小问题：Traversing a graph breadth first, marking visited nodes in Haskell）。

Answer 3

应该注意的是，图中最长的路径与生成树中最长的路径 不一样。图可以有很多生成树，并且这些树没有 具有相同的高度。 由duplode提供的btf代码正确地找到了生成树中最长的路径。

例如，在duplode答案 mkUGraph [1..7] [(1,3),(1,2),(2,4),(3,5),(2,6),(5,2),(5,7)] 图形具有然后更长的路径的一个建议的[1,3,5,7]，该路径是[1,3,5,2,6]。

mkUGraph [1,2,3] [(1,2),(1,3),(2,3)] 使用的光纤光栅激光器的一个更简单的例子btf 1将产生生成树[[1], [3,1], [2,1]]和最长路径是[1,2,3]（和由本身是一个生成树）。一般来说，找到最长路径并不是微不足道（实际上是NP-hard），但是可以使用拓扑排序节点的相当直接的折叠来完成DAG。

见 https://github.com/rpeszek/graph-exercise