Обратный Ширина Первый обход в C #

Question

У кого-нибудь есть готовая реализация алгоритма обратного обхода первой ширины в C #?

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

Давайте посмотрим на рисунок ниже, это вывод обхода Breadth First:

В моем обратном первом проходе в ширину 9, 10, 11 и 12 будут первые несколько найденных узлов (порядок их не важен, так как все они первого порядка). 5, 6, 7 и 8 - вторые найденные узлы и т. Д. 1 будет последним найденным узлом.

Есть идеи или указатели?

Редактировать: Измените "Поиск в ширину" на "Обход в ширину", чтобы прояснить вопрос

Answer 1

Используйте комбинацию стека и очереди.

Выполняйте «обычную» BFS, используя очередь (которую, я полагаю, вы уже знаете, уже делаете), и продолжайте помещать узлы в стек по мере их появления.

После завершения работы с BFS стек будет содержать обратный порядок BFS.

Answer 2

Запустите нормальную BFS из rootNode и позвольте depth[i] = linked list of nodes with depth i. Так что для вашего примера у вас будет:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. Вы можете построить это с помощью простого поиска BFS. Затем выведите все узлы в depth[maxDepth], затем узлы в depth[maxDepth - 1] и т. Д.

Глубина узла i равна глубине его родительского узла + 1. Глубину корневого узла можно считать 1 или 0.