Обратный ширину первый обход в C #

Question

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

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

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

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

Любые идеи или указатели?

Редактировать: Изменить «Широчный поиск» в «Ширина первого прохождения», чтобы уточнить вопрос

Answer 1

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

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

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

Answer 2

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

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

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