В чем разница между первым поиском по ширине и обходом уровня?

Мне не нужен код, просто объяснение. В моем учебнике говорится

Мое понимание первого поиска по ширине заключается в том, что сначала вы исследуете узлы, расположенные ближе всего к корню, начиная с левой? Как это иначе? Это квадратная и прямоугольная ситуация?

Ответы

Ответ 1

Для "правильного" дерева (см. ниже) это то же самое, по крайней мере, по большинству определений. Например Wikipedia, например:

Ширина первой

Смотрите также: Поиск по ширине

Деревья также могут пересекаться в уровне,...

... обход ширины (уровень)...

Ну, по крайней мере, обход уровня порядка совпадает с обходом с шириной в ширину. Есть много причин, по которым можно что-то пересечь, это не просто поиск, поскольку, как кажется, подразумевается широкий поиск, хотя многие (или большинство) не делают этого различия и используют термины взаимозаменяемы.

Единственный раз, когда я лично использовал "обход уровня", - это когда речь идет о внутри, после и предварительном обходе, просто следовать тот же формат "... -порядка порядка".

Для общего графика понятие "уровня" может быть не совсем корректным (хотя вы можете просто определить его как кратчайшее расстояние от источника node, я полагаю), таким образом, уровень-порядок обход не может быть четко определен, но поиск по ширине по-прежнему имеет смысл.

Я упомянул "правильное" дерево выше (которое является полностью составленной подклассификацией, на случай, если вам интересно) - это просто означает, что "уровень" определяется так, как вы ожидали, - каждый край увеличивает уровень на один, Тем не менее, можно немного поиграть с определением "уровень" (хотя это может быть не принято), по существу позволяя ребрам перепрыгивать уровни (или даже иметь края между узлами на одном уровне). Например:

level
  1          1
            / \
  2        /   3
          /   /
  3      2   4

Таким образом, обход уровня будет 1, 3, 2, 4,
в то время как обход ширины был бы 1, 2, 3, 4.

Ответ 2

мы используем обход уровня порядка для деревьев, потому что в деревьях нет цикла, и как только узел посещается, он не собирается посещать снова, но на графиках это не так. График также может быть циклическим, и если график циклический, в соответствии с порядком уровней, если узел посещен, он не проверяет, посещен он или нет, и снова он будет проходить один и тот же узел бесконечное число раз. и программа продолжит движение из-за цикла. Таким образом, мы используем BFS или DFS в случае графа.