Если я правильно понимаю проблему, то, возможно, будет быстрее, если вы начнете снизу и найдете узлы, идущие вверх.
Поскольку вы знаете подмножество детей (E *), которое вы хотите найти, если вы начинаете с целевых потомков, все родители по определению являются частью результата, и вам не нужно фильтровать.
В простом итеративном подходе Python, что-то вроде этого будет искать все родительские узлы для "E *" children:
(Обратите внимание, что я добавил дополнительную строку с "BB3 DD1 AA2", чтобы иметь еще один дубликат.)
data = """AA1 BB1 AA1
AA1 BB2 AA1
BB2 CC1 AA1
AA2 BB3 AA2
AA2 BB4 AA2
BB4 CC1 AA2
BB3 DD1 AA2
BB4 DD1 AA2
DD1 EE1 AA2
DD1 EE2 AA2
BB4 FF1 AA2
FF1 GG1 AA2
GG1 EE3 AA2"""
# tuple (parent, child, root)
tuples = {tuple(l.split()) for l in data.split("\n")}
parentsByChild = {}
for node in tuples:
p = set(parentsByChild.get(node[1], frozenset()))
p.add(node)
parentsByChild[node[1]] = frozenset(p)
# alternatively:
# from itertools import groupby
# parentsByChild = {c:frozenset(nodes) for c, nodes in groupby(sorted(tuples, key=lambda n: n[1]), lambda n: n[1])}
def expand(nodes):
todo, found = set(nodes), set()
while todo:
node = todo.pop()
if not node in found:
found.add(node)
todo.update((p for p in parentsByChild.get(node[0], set()) if p not in found))
return found
leaves = {n for n in tuples if n[1].startswith("E")}
for t in expand(leaves):
print(t)
Это должно быть линейным числом ребер: мы перебираем их один раз, чтобы собрать кортежи, и второй раз, чтобы сгруппировать родителей. Вызов expand перебирает всех «интересных» детей и их родителей, расширяя родителей только для новых узлов, поэтому мы никогда не работаем дважды для одного и того же узла.