Кто-нибудь имеет готовую реализацию алгоритма обратного пересечения первого прохода в С#?
По обратному пересечению Первый обход, я имею в виду вместо поиска дерева, начинающегося с общего node, я хочу искать дерево снизу и постепенно сходиться к общему node.
Посмотрим на приведенный ниже рисунок, это результат первого пересечения Ширина:
В моем первом обратном круге, 9, 10, 11 и 12 будут найдены первые несколько узлов (порядок их не важен, так как они все в первом порядке). 5, 6, 7 и 8 - это несколько найденных узлов и т.д. 1 будет последним найденным node.
Любые идеи или указатели?
Изменить: изменить "Первый поиск по ширине" на "Обход пятого пути", чтобы прояснить вопрос
Запустите нормальную 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.
Используйте комбинацию стека и очереди.
Сделайте "нормальную" BFS с помощью очереди (которую, как я полагаю, вы уже знаете, уже сделали), и продолжайте нажимать узлы в стеке, когда вы сталкиваетесь с ними.
После выполнения с BFS, стек будет содержать обратный порядок BFS.