Мысли о рекурсивном алгоритме
У меня есть проблема под рукой, которая может быть указана следующим образом.
Существует два набора узлов (в двустороннем ориентированном графе), type1 и type2.
Для каждого узла в графике type1 я должен узнать набор, который создается этим способом:
Позвольте node1 быть первым узлом type1.
Добавьте node1 в наборе. Для node1 узнайте список узлов type2, соединенного через край, кто источник, node1. Для каждого участника в списке, полученном выше, уже найдите узлы типа 1 (не в наборе) соединенными через край, кто цель, узел type2. Добавьте те узлы в наборе. Повторно выполненный, до нет ничего для добавления в наборе.
Выполните итерации для всех узлов type1.
Моя интуиция идет к рекурсивной реализации, но не может выяснить на том, что (перепутали) параметры.
Какие-либо предложения?
2 ответа
Похоже, вы можете изменить алгоритм поиска в ширину (который можно реализовать с помощью очереди).
Поскольку он направлен, для узлов существует полный порядок.
Вы можете использовать поиск в глубину структуры.
def visit( some_node, type_1_set ):
assert node.type == 1
type_1_set.add( some_node )
for child in some_node.children:
if child.type == 2:
for grand_child in child.children:
if grant_child.type == 1:
visit( grand_child, type_1_set )
Это звучит примерно так.