BFS есть пропущенный параметр?

Question

У меня есть следующий код для выполнения BFS на графике:

open Queue 


type 'a node = {id: 'a; edges: 'a list}
type 'a graph = 'a node list


let bfs g s = 
    let seen = Array.make (Array.length g) false
    and treated = Queue.create() in 
    Queue.add s treated ; seen.(s) <- true ;
    let rec add_neighbors = function
    |[]                    -> ()
    |t::q when seen.(t)  -> add_neighbors q
    |t::q                  -> Queue.add t treated ; seen.(t) <- true ; add_neighbors q
    in
    try while true do 
      let s = Queue.take treated in 
      print_int s ;
      add_neighbors g.(s)
      done
    with Empty -> ()

Проблема в том, что я не понимаю, как работает функция bfs.Сначала мы даем граф g и первый узел s, но затем функция add_neighbors выглядит следующим образом:

let rec add_neighbors = function

Проблема здесь в том, что эта функция ожидает аргумент, но яне вижу, где в коде мы передаем этот аргумент функции add_neighbors.

Чтобы быть более точным.Допустим, у меня есть график g, и я хочу выполнить BFS на этом графике, начиная с узла s.

Поэтому я вызываю функцию bfs g s.Итак, вот что делает функция:

• создание массива с именем seen со всеми записями, равными false
• создание очереди с именем treated, в которую мы добавляемузел s
• обновляем значение узла s в массиве seen.Так что теперь в массиве seen значение s равно true
• Вот проблема для меня.Мы вызываем здесь рекурсивную функцию с именем add_neighbors, но эта функция ждет здесь аргумента, но вот какой аргумент мы даем этой функции?Как алгоритм продолжает отсюда?

Answer 1

функция [создает] массив с именем seen […], [создает] очередь с именем treated […], [и обновляет] значение узла s в массивеseen.
[Тогда] мы вызываем здесь рекурсивную функцию с именем add_neighbors, но эта функция ждет здесь аргумента, но какой аргумент мы даем этой функции?

Нет, let rec add_neighbors = function не вызывает функцию. объявляет локальную переменную add_neighbors со значением функции, а затем позволяет использовать эту переменную in в следующем блоке.

Как алгоритм продолжает отсюда?

Следующее, что выполняет алгоритм, это блок

try while true do 
  let s = Queue.take treated in 
  print_int s ;
  add_neighbors g.(s)
  done
with Empty -> ()

В бесконечном цикле он берет первый узел из очереди treated, печатает его и затем вызывает add_neighbors с теми, которые предположительно являются соседями узла s.Этот вызов g.(s) (или Array.get g s) предполагает, что g относится не к типу graph, а к массиву списков, причем индекс массива является идентификатором узла, из которого происходят некоторые ребра, а значения списка являются узломИдентификатор того, куда указывают ребра.

Этот бесконечный цикл заканчивается, когда операция Queue.take выдает исключение Empty, которое перехватывается и обрабатывается бездействием.Я бы сказал, что лучше вместо этого написать

while not (Queue.is_empty treated) do 
  let s = Queue.take treated in 
  print_int s ;
  add_neighbors g.(s)
done