python中的多节点图到单节点图

Question

我有一个Directed Acyclic图，如下所示：

[a, b, c] --> [p, q] --> [p, a, c] --> [x, y, z]

这里，每个字母表都是一个节点。从上图中，我想要所有具有单个节点的图表的列表。例如，一个图可以是：a --> p --> a --> y另一个可以是：b --> p --> p --> z等。

我可以在主图上做一个DFS来遍历它，但我不知道如何做多个DFS来提取每个具有单个字符的图形

Answer 1

如果你有一个节点集列表，你可以做这样的事情 -

from itertools import product
s =[[1, 2], [3, 4, 5], [6, 7]]
list(product(*s))

输出 -

[(1, 3, 6), (1, 3, 7), (1, 4, 6), (1, 4, 7), (1, 5, 6), (1, 5, 7), (2, 3, 6), (2, 3, 7), (2, 4, 6), (2, 4, 7), (2, 5, 6), (2, 5, 7)]