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

Question

我有一个有向无环图，如下所示：

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

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

我可以DFS在主图上进行DFS深度优先搜索（

标签： pythonrecursiondata-structuresdepth-first-search

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)]