Ocaml: Самый длинный путь

Question

Я должен сделать алгоритм для самой длинной проблемы пути.

У меня есть ориентированный взвешенный граф, начальный узел, стоп-узел и число k.

Алгоритм должен сказать, существует ли на графике путь от начального узла до остановки узла с длиной не менее k.

Настоящая проблема заключается в том, что я должен использовать BFS-посещение algortihm, а не DFS. На OCAML РСПЛС использовать очереди и узел являются вставки на конец структуры:

let breadth_first_collect graph start = 
     let rec search visited = function 
      [] -> visited 
      | n::rest -> if List.mem n visited 
       then search visited rest 
       else search (n::visited) (rest @ (succ graph n)) 
       (* new nodes are put into queue *) 
in search [] [start];; 

Кто-то может дать мне некоторые советуют, даже theorical, чтобы сделать это?

Answer 1

В BFS вы в основном не должны углубляться, прежде чем закончите текущий слой. Это означает, что на каждом шаге вы должны взять набор преемников, вырезать данные и впоследствии перезаписывать каждый из них подряд. Вот первое приближение (непроверенное) алгоритм:

let breadth_first_collect succ graph start = 
    let rec search visited v = 
    let succs = succ graph v |> 
       List.filter (fun s -> List.mem s visited) in 
    List.map (search (succs @ visited)) succs |> List.concat in 
    search [] start 

Итак, первый визит всех дети (ака succs) предварять в очередь, и рекурсивно спуск в каждый ребенок в ряде.

Снова это в первом приближении. Поскольку вам нужно знать длину пути, это означает, что вам нужно хранить каждый путь в очереди отдельно и не просто иметь набор всех посещенных вершин. Это означает, что ваша очередь должна быть vertex list list. В этом случае вы можете собрать все возможные пути и найти, существует ли он, который больше k.