мелкие узлы и более глубокие узлы

Question

Я обнаружил, что в каком-то уроке первый поиск в ширину

расширяет мелкие узлы до более глубоких узлов.

Я действительно запутался, что означает каждый из них?

Спасибо

Answer 1

Термины «мелкий» и «глубокий» происходят от визуализации вашего графа с начальным узлом вверху: «глубина» узла - это число ребер, которые вам нужно пройти, чтобы добраться до этого узла из начальный узел. Утверждение о BFS говорит вам, что узлы с меньшим количеством ребер между ними и начальным узлом обнаруживаются до того, как узлы отделены от начала большим количеством ребер.

Answer 2

Это означает, что если вы вычислите длину L(v) кратчайшего пути от начального узла к каждому отдельному узлу v в вашем графе, то BFS-узлы с меньшим L(v) всегда обрабатываются до узлов с более высоким L(v).

Более простое объяснение: BFS всегда запускается и обрабатывает все узлы, которые являются прямыми соседями начального узла.Затем он обрабатывает всех прямых соседей прямых соседей начальных узлов (исключая уже обработанные) и т. Д.

Последними узлами, которые должны быть обработаны, являются те, которые имеют наибольшее расстояние от начального узла.