在有向无环图中寻找路径，给定目的地。

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)]

如果我正在寻找第二个人或者

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

如果我对第三个人感兴趣。

我能做到吗？如果可以，如何做？除了map之外，是否有其他结构更适合实现这一点？

非常感谢您的帮助。

- Steven

---

当我评论更改标题时，我以为你想要提出一个新问题，经过思考后，我明白了你的意思。我已经更改了标题，但由于这是你的问题，如果这不适合你，显然你应该将其更改为其他内容。 - Guy Coder

Answer 1

我假设您想要获取一组由整数对组成的列表，这些整数直接或间接地报告给某个“根”。以下是一个简单但效率低下的解决方案：

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

let reportStructureSet = 
    reportStructure |> Set.ofArray

let reportingDirectlyTo root raportsToSet = 
    raportsToSet 
    |> Set.filter(fun (_, key) -> key = root) 

let addNextGeneration previousIteration raportsToSet = 
    let numbersLowerInHierarchy = previousIteration |> Set.map fst
    raportsToSet |> Set.filter(
        // select only those elements from raportsToSet...
        fun (num, supervisor) -> 
            // ...which either are already in previousIteration 
            (Set.contains (num, supervisor) previousIteration) || 
            // ...or are "below" someone from previousIteration
            (Set.contains supervisor numbersLowerInHierarchy))

let reportingDirectlyOrIndirectlyTo root raportsToSet = 
    // applies addNextGeneration until is "stabilizes" on some value
    let rec fixPointHelper previousIteration = 
        let nextIteration = addNextGeneration previousIteration raportsToSet
        if nextIteration = previousIteration
            then nextIteration
            else fixPointHelper nextIteration

    // set of numbers directly reporting to root
    let reportsDirectly = reportingDirectlyTo root raportsToSet
    // start "iteration" using numbers directly reporting to root
    fixPointHelper reportsDirectly

let reportingDirectlyOrIndirectlyToList root raportsToSet =
    reportingDirectlyOrIndirectlyTo root raportsToSet
    |> Set.toList

如果您想实现一个高效的解决方案，您应该按照以下方式将reportStructureSet解释为图形：

• int是顶点
• 一对int是有向边

然后，只需使用DFS检查从“根”可达的边。

- Tomasz Maczyński

Answer 2

由于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)]

- Guy Coder

---

你之前的评论启发我自己用F#编写DFS算法，作为一个相对新手来说是具有挑战性的，但是你在这里提供的内容和原始来源链接非常有帮助。谢谢！现在我知道这个问题被称为“拓扑排序”，我想知道是否更改问题标题会有所帮助。你有什么想法吗？这可能有助于未来的搜索。 - Steven

由于您的问题已经有两个基于DFS（深度优先搜索）的答案，我建议您放弃这个问题并开始一个新的问题。即使问题非常类似于这个问题，在回答给出后更改问题也是不被赞同的。此外，提出一个新问题将会获得更多积分。 :) 只需确保新问题足够不同，以免被标记为重复。 - Guy Coder

我没有使用拓扑排序来回答问题，而是使用了深度优先搜索。我开始使用拓扑排序，但因为它比DFS更复杂，而且你刚接触F#，所以不想给你提供一个比必要的更复杂的答案。 - Guy Coder

要更改标题，只需单击编辑即可（我知道它是灰色的，但它是活动的） - Guy Coder

经过思考，你在更改标题方面的评论是正确的，你应该只为这个问题更改标题。我原本认为你想把单词“ToplogicalSort”放在标题中，但不应该如此。作为建议，将其设置为能够吸引注意力的内容，并且您应该会获得更多的投票，但不要太普遍，否则像我这样的人会更改它。例如，“如何在给定目标的图中找到路径”。 - Guy Coder

Answer 3

我喜欢F#难题，所以我尝试了这一个。希望你们喜欢。

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

let orgMap =
    orgList
    |> List.fold (fun acc item -> 
        let key = snd item
        match Map.tryFind key acc with 
        | Some(value) -> 
            let map' = Map.remove key acc
            Map.add(key) (item::value) map'
        | None -> 
            Map.add(key) (item::[]) acc
        ) Map.empty<int, (int*int) list> 

let findReports supervisor = 
    let rec findReports' acc collection = 
        match collection with 
        | head::tail -> 
            (findReports' (head::acc) tail) 
            @   match Map.tryFind (fst head) orgMap with
                | Some(value) -> (findReports' [] value)
                | None -> []
        | [] -> acc    
    findReports' [] (Map.find supervisor orgMap)    

findReports 2
|> List.map fst
|> List.distinct

返回

val it : int list = [3; 4; 5; 7; 6]

findReports 2 返回

val it : (int * int) list = [(3, 2); (4, 2); (5, 3); (7, 3); (6, 4)]

---

我会分解它以便澄清。

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

我们将接收到的元组列表转换为一个以老板为键，值为((报告人，老板)列表)的函数映射。这也可以被称为邻接表，用于遍历图形。

let orgMap =
    orgList
    |> List.fold (fun acc item -> 
        let key = snd item
        match Map.tryFind key acc with 

如果有一份老板名下的报告列表，就将其添加到该列表中。

        | Some(reports) -> 
            let map' = Map.remove key acc
            Map.add(key) (item::reports) map'

否则，将其添加到空列表中并插入字典中。

        | None -> 
            Map.add(key) (item::[]) acc

以一个空映射作为累加器开始。

        ) Map.empty<int, (int*int) list> 

通过递归遍历项目以查找所有报告。

let findReports supervisor = 
    let rec findReports' acc collection = 
        match collection with 

如果有一个项目，将其附加到累加器中。这是BFS。如果在连接运算符（@）之前和之后切换表达式，则会变成DFS。

        | head::tail -> 
            (findReports' (head::acc) tail) 

将当前列表连接到报告的递归列表以形成报告。

            @   match Map.tryFind (fst head) orgMap with
                | Some(value) -> (findReports' [] value)
                | None -> []

如果在列表末尾，返回该列表。

        | [] -> acc    

运行递归函数。

    findReports' [] (Map.find supervisor orgMap)    

运行该函数。

findReports 7

只返回报告

|> List.map fst

不要重复报告已经报告过的问题。

|> List.distinct

- Phillip Scott Givens