2
я обнаружили, что в каком-то учебнике ширина первого поискамелких узлы и глубокие узлы
мелкие узлы расширяется Befor глубоких узлов.
Я действительно запутался в чем смысл каждого из них?
Спасибо
A
ответ
3
Термины «неглубокие» и «глубокие» исходят из визуализации вашего графика с начальным узлом вверху: «глубина» узла - это количество ребер, которые нужно пройти, чтобы добраться до этого узла из начальный узел. Утверждение о BFS говорит вам, что узлы с меньшим количеством ребер между ними и стартовым узлом обнаруживаются до того, как узлы отделены от начала большим количеством ребер.
2
Это означает, что если вы вычислить длину L(v) кратчайшего пути от исходного узла к каждому отдельному узлу v в вашем графике, с BFS узлами с более низким L(v) всегда обрабатываются до узлов с более L(v).
Простые пояснения: BFS всегда запускает и обрабатывает все узлы, которые являются непосредственными соседями исходного узла. Затем он обрабатывает все прямые соседи прямых соседей стартовых узлов (исключая уже обработанные) и т. Д.
Последние обрабатываемые узлы - это те, у которых наибольшее расстояние от начального узла.
Хорошо, но скажем, что у нас есть дерево с тремя узлами, правый ребенок и левый ребенок имеют одинаковую глубину от корня, (равно числу ребер, так? Зачем сначала развернуть левый ребенок? –
@ JasmineAl-Qahtani Правый и левый узлы в вашем примере находятся на одной и той же глубине. В заявлении от OP ничего не говорится о порядке расширения узлов на одной и той же глубине: по отношению к алгоритму BFS порядок расширения сестры может быть случайным – dasblinkenlight
Вы имеете в виду, что я могу вывести любой узел из узлов с одинаковой глубиной (sibling)? –