c++ - 从文本文件中检测有向图中的循环

Question

我正在尝试从文本文件中读取值，然后确定它表示的图形是否为 DAG。我想知道在时间效率方面最快的方法是什么。

这是文本文件

3
2
1,2,
2,3

我正在考虑使用给定的信息制作邻接列表，然后从那里移动。非常感谢任何帮助

Answer 1

一种方式，虽然可能不是最快的方式，是到topologically sort图。当且仅当算法失败时，该图才有循环(参见 Kahn's algorithm )。

运行时间是O(|V| + |E|)，其中|V|是顶点数，|E| 是边的数量。

Bender 等人发表了一篇论文。 (Robert Tarjan 是作者之一)，A NEW APPROACH TO INCREMENTAL CYCLE DETECTION AND RELATED PROBLEMS ，您可能想看一看。

另一篇相关论文是 Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance bu Haeupler 等人。 (Tarjan 再次成为作者之一)。