python - 在循环有向图中检测多个循环

Question

我有一个有向循环图，其中包含多个循环，我需要一种方法来检测（并列出）有向图中存在的每个循环。

这是为了调试我的 python 脚本而放在一起的虚拟图。它包含循环：

[n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7]

该算法必须检测有向图中的每个循环，而不仅仅是最小的也不是它遇到的第一个。

score 2 · Accepted Answer

您并没有真正指定如何表示有向图，但您可以查看Neopythonic:Detecting Cycles indirected graph。

score 1 · Accepted Answer

AFAIK，python-graph 只找到一个循环，而不是所有可能的循环。看：

This other article似乎解决了这个问题中提出的问题：

它使用的是 RE Tarjan 在 1972 年设计的算法

score 0 · Accepted Answer

0

您可能想尝试使用这个库。它有一个循环检测算法。

于 2011-06-19T08:38:52.933 回答

3 回答 3