是否可以（快速）找到 networkx 图中的第一个循环？

Question

我有一个有向网络，其中可能有也可能没有循环。我需要找到它们并消除循环。如果我有一个 networkx DiGraph (G)，我可以找到所有的循环cycle_nodes = nx.simple_cycles(G)这创建了一个循环返回生成器。但是，我不想返回所有循环，list(cycle_nodes)因为许多循环都是彼此的子集，修复一个将修复其他循环。相反，我只想找到循环的第一个实例。作为cycle_nodes发电机，我试过next(cycle_nodes)只返回第一个实例。但是，我发现返回第一个实例所需的时间与返回所有实例所需的时间相比并不小：list(cycle_nodes) : 58snext(cycle_nodes) : 44s这仅仅是由于我的图表的性质（即第一个循环沿着搜索顺序很远），还是有更有效的方法来返回任何循环（不一定需要是第一个）？我怀疑可能有更快的方法的原因是因为当我运行时nx.is_directed_acyclic_graph(G)，它只需要一两秒钟并返回 False，所以它显然在一秒钟左右找到至少一个循环。

Answer 1

答案是显而易见的。没有提供起始节点的算法 nx.find_cycle() 将快速返回它找到的第一个循环。我的印象是需要提供一个起始节点，RTFM！