在有向无环图中,如果将有向无环图的所有边都添加到有向无环图中,找到这些边的最快方法是什么?
形式上:假设有一个DAG$G=(V,E)$,边集为$E\subset V\times V$找出V乘以V-e$中的所有$e,使得图$G(e)=(V,e\cup{e})$至少有一个循环。
暴力方法是使用DFS检查$G(e)$是否在V\times V-e$中的所有$e有一个周期有更快的方法吗?
最佳答案
观察:当且仅当一条边是自循环或其反向边属于DAG的transitive closure时,该边才诱导一个循环因此,计算传递闭包的问题实质上等同于这个问题可悲的是,理论上最快的已知算法是基于快速矩阵乘法的,因此毫无希望地不切实际。
如果您对实际计算大型DAG的传递闭包感兴趣,Wikipedia会链接到Esko Nuutila's thesis on the subject。