BFS плохая сложность

Question

Я использую списки смежности для представления графа в OCaml.Затем я сделал следующую реализацию BFS в OCaml, начиная с узла s.

let bfs graph s=
    let size = Array.length graph in
    let seen = Array.make size false and next = [s] in 
    let rec aux  = function 
    |[] -> ()
    |t::q -> if not seen.(t) then  begin seen.(t) <- true;  aux (q@graph.(t)) end  else aux q 
    in aux next

size представляет количество узлов графа.seen - это массив, где seen.(t) = true, если мы видели узел t, а next - это список узлов, которые нам нужно увидеть.

Дело в том, что обычно сложность временидля BFS является линейным (O (V + E)), но я чувствую, что моя реализация не имеет такой сложности.Если я не ошибаюсь, сложность q@graph.(t) достаточно велика, поскольку она O (| q |).Так что моя сложность довольно плохая, так как на каждом этапе я объединяю два списка, и это тяжело по времени.

Таким образом, мне интересно, как я могу адаптировать этот код, чтобы сделать эффективную BFS?Проблема (я думаю) исходит от реализации очереди с использованием списков.Принимает ли сложность модуля Queue в OCaml O (1) для добавления элемента?В таком случае, как я могу использовать этот модуль для работы моего bfs, так как я не могу выполнить сопоставление с шаблоном с очередью так же легко, как со списком?

Answer 1

Если я не ошибаюсь, сложность q @ graph. (T) довольно велика, поскольку она O (| q |).

Это действительно проблема. То, что вы должны использовать, это graph.(t) @ q. Сложность этого O (| graph. (T) |).

Вы можете спросить: какая разница?

Разница в том, что | q | может быть любым от 0 до V * E. graph. (t) с другой стороны, вы можете работать с. Вы посещаете каждую вершину графа не более одного раза, поэтому общая сложность будет

  O(\Sum_V |grahp.(v))

Сумма всех ребер каждой вершины графа. Или другими словами: E.

Это подводит вас к общей сложности O (V + E).

Answer 2

сложность q @ graph. (T) довольно большая, так как она O (| q |). Так что моя сложность довольно плохая, так как на каждом шаге я объединяю два списка, и это тяжело по времени.

Вы абсолютно правы - это узкое место вашей BFS. Вы должны с радостью использовать модуль Queue, потому что согласно https://ocaml.org/learn/tutorials/comparison_of_standard_containers.html операция вставки и извлечения элементов равна O (1).

Одно из различий между очередями и списками в OCaml заключается в том, что очереди являются изменяемыми структурами, поэтому вам нужно будет использовать не чистые функции, такие как add, take и top, которые соответственно вставляют элемент на месте, pop элемент спереди и вернуть первый элемент.