Поиск в ширину (BFS) - PullRequest
Новая
       27

Поиск в ширину (BFS)

2 голосов
/ 15 января 2020

Я изучаю алгоритм BFS, и у меня только что возник вопрос относительно того, как соседние узлы вставляются в очередь.

Например, предположим, что мы имеем дело с неориентированным графом и мы хотим выполнить BFS для вывода содержимого графа, тогда как мы узнаем, какой порядок соседних узлов вставлен в очередь после того, как начальный узел был извлечен из очереди? Кроме того, есть ли способ изменить, как соседние узлы вставляются в очередь?

Любая помощь будет высоко ценится, спасибо.

1 Ответ

1 голос
/ 15 января 2020

Порядок вставки братьев и сестер (соседей) полностью определяется кодом, который их вставляет - с теоретической точки зрения требования отсутствуют. Требование BFS состоит в том, что все узлы на глубине k проходят перед любыми узлами на глубине k+1.

Например, для данной очереди q и root узел root: 

q.enqueue(root);

while(!q.isEmpty()) {
     Node n = q.dequeue();

     <process n>

     // add children to queue
     for (Node child : n.getChildren()) {
          q.enqueue(child);
     }
}

, поэтому, если бы это началось с n как root дерева, оно проходило бы через все дерево в порядке уровней, то есть в ширину. Итак, вы спрашиваете, в каком порядке вставляются дети? Ну, это зависит только от того, какой порядок getChildren() проходит через узлы (в этом примере). Другие реализации могут сортировать их и добавлять их в этом порядке. Или иметь порядок связанных списков для детей под родителем. Или выберите случайным образом.

Если узлы имеют числовые значения, а дерево имеет формат 

1
1.1 1.2          1.3
    1.2.1 1.2.2  1.3.1

, код может быть настроен для перебора дочерних элементов в числовом порядке. Он будет обрабатывать 1, добавлять свои дочерние элементы (1.1, 1.2, 1.3) в очередь, обрабатывать 1.1, добавлять свои дочерние элементы (нет) в очередь, обрабатывать 1.2, добавлять свои дочерние элементы (1.2.1, 1.2.2) в очередь. , обработайте 1.3 и его дочерние элементы (1.3.1) в очередь, а затем перейдите на третий уровень.

Если вы хотите изменить порядок, вы можете (A) изменить код logi c где узлы добавляются в очередь, указывая конкретный способ выбора следующего потомка для pu sh, а не просто слепой итерации, (B) измените / переопределите итерационную функцию getChildren(), которую вызывает блок enquque, или ( C) если вы знаете метод итерации, но не можете изменить код, вынудите дерево иметь настройку, которую итеративная функция будет проходить нужным вам способом, например, переименовывая узлы или связывая их в структура определенным образом. Вариант (B), вероятно, предпочтительнее.

Поскольку вы говорите, что график «ненаправленный», похоже, что, возможно, вы не можете контролировать порядок самого графика, поэтому опция (C) не будет работать в любом случае. Поэтому, если вы хотите контролировать порядок дочерних элементов, вам нужно будет заставить итеративный код каким-то образом сортировать узлы, чтобы получить согласованный результат.

...