Обратный Обход вершин в ширину в C#
У кого-либо есть готовая реализация Обратного алгоритма Обхода вершин в ширину в C#?
Обратным Обходом вершин в ширину я имею в виду вместо того, чтобы искать дерево, начинающее с общего узла, я хочу искать дерево от нижней части и постепенно сходился к общему узлу.
Давайте посмотрим ниже числа, это - вывод Обхода вершин в ширину: 
В моем обратном обходе вершин в ширину, 9,10,11 и 12 будут первые несколько найденных узлов (порядок их не важны, поскольку они - весь первый порядок). 5, 6, 7 и 8 вторые немного найденных узлов, и так далее. 1 был бы последний найденный узел.
Какие-либо идеи или указатели?
Править: Измените "Поиск в ширину" на "Обход вершин в ширину" для разъяснения вопроса
2 ответа
Запустите обычную BFS из rootNode и пусть depth [i] = связанный список узлов с глубиной i . Итак, для вашего примера у вас будет:
глубина [1] = {1}, глубина [2] = {2, 3, 4} и т. Д. . Вы можете создать это с помощью простого поиска BFS. Затем выведите все узлы в глубину [maxDepth] , затем узлы в глубине [maxDepth - 1] и т. Д.
Глубина узла i равна равна глубине его родительского узла +1. Глубину корневого узла можно считать 1 или 0.
Используйте комбинацию стека и очереди.
Выполните «нормальную» BFS, используя очередь (что, я полагаю, вы уже знаете, что делать), и продолжайте вставлять узлы в стек по мере их появления.
После завершения работы с BFS стек будет содержать обратный порядок BFS.