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

Кто-нибудь имеет готовую реализацию алгоритма обратного пересечения первого прохода в С#?

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

Посмотрим на приведенный ниже рисунок, это результат первого пересечения Ширина:

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

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

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

Ответ 1

Запустите нормальную 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] и т.д.

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

Ответ 2

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

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

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