我正在尝试从文本文件中读取值，然后确定它表示的图形是否为 DAG。我想知道在时间效率方面最快的方法是什么。
这是文本文件
3
2
1,2,
2,3
我正在考虑使用给定的信息制作邻接列表，然后从那里移动。非常感谢任何帮助
最佳答案
一种方式，虽然可能不是最快的方式，是到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 再次成为作者之一)。
关于c++ - 从文本文件中检测有向图中的循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36344242/