在给定目的地的(DAG)有向无环图中寻找路径

Question

假设我有这个数组:

let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|]

int元组中的第一个向第二个报告的位置int.

我可以很容易地映射它

let orgMap = Map.ofArray reporting

从那里,我可以很容易地得到所有向2报告的整数列表

orgMap 
|> Map.filter (fun _ key -> key = 2)

返回

map [(3, 2); (4, 2)]

然而,我真正希望看到的是整个结构,从2一直向下.例如,我想找到一种方法可以给我样本输出

map [(3, 2); (4, 2); (5, 3); (6, 4); (7, 3)]

如果我正在找人2或

map [(5, 3); (7, 3)]

如果我对人3感兴趣

我可以这样做吗？如果是这样,怎么样？是否有其他结构map可以更好地实现这一目标？

在此先感谢您的帮助.

Answer 1

由于 OCaml 与 F# 很接近，并且尝试在 F# 中查找拓扑排序并没有找到任何有用的信息，因此我寻找了 OCaml 代码。

我找到了《Objective Caml 简介》，其中使用深度优先搜索解决了您的问题，并将其用作此答案的基础。另外，由于您是 F# 新手，因此您可以查看文档并了解代码是如何派生的。奇怪的是，我在发布此内容后查看了文档的其余部分，他在文档后面有一个更高级的 DFS 版本。

您的输入是一个数组[| |]，但您的答案是一个列表[]，因此我将大部分工作作为列表完成。

答案的顺序与您的顺序不同，但格式相同。

    let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|]

    //
    //  6 -> 4 -> 2
    //  5 -> 3 -> 2 -> 1 
    //  7 -> 3

    // val revStructure : tl:('a * 'b) list -> ('b * 'a) list
    let revStructure tl = List.map (fun (a,b) -> (b,a)) tl

    // val mem : item:'a -> list:'a list -> bool when 'a : equality
    let mem item list = List.exists (fun x -> x = item) list 

    // val successors : n:'a -> edges:('a * 'b) list -> 'b list when 'a : equality
    let successors n edges = 
        let matching (s,_) = s = n
        List.map snd (List.filter matching edges)

    // val dist : pred:'a -> succs:'b list -> ('a * 'b) list
    let dist pred succs = List.map (fun y -> (pred,y)) succs

    // val dfsPairs : edges:('a * 'a) list -> start:'a -> ('a * 'a) list when 'a : equality
    let dfsPairs edges start =
        let rec dfsPairsInner edges visited start result = 
            match start with 
            | [] -> List.rev (revStructure result) 
            | n::nodes -> 
                if mem n visited then 
                    dfsPairsInner edges visited nodes result
                else 
                    let predecessors = dist n (successors n edges)
                    let result =
                        match predecessors with
                        | [] -> result
                        | _ -> predecessors @ result
                    dfsPairsInner edges (n::visited) ((successors n edges) @ nodes) result
        dfsPairsInner edges [] [start] []

    let revEdges = revStructure (List.ofArray reportStructure)

    let result = dfsPairs revEdges 2
    // val result : (int * int) list = [(4, 2); (3, 2); (7, 3); (5, 3); (6, 4)]

    let result = dfsPairs revEdges 3
    // val result : (int * int) list = [(7, 3); (5, 3)]