Fre*_*ool 2 algorithm graph-theory cycle
给定一个无向图,检测它是否包含循环的最佳算法是什么？
在跟踪被访问节点的同时进行广度优先或深度优先搜索是一种方法,但它是O(n ^ 2).有什么更快的吗？
Art*_*ger 5
给定图G(V,E)的BFS和DFS算法具有O(| V | + | E |)的时间复杂度.所以你可以看到它是输入的线性依赖.如果你有非常专业的图形,你可以执行一些启发式方法,但一般情况下使用DFS并不是那么糟糕.您可以在这里查看一些信息.无论如何,你必须遍历整个图表.
归档时间：
16 年，5 月 前
查看次数：
4966 次
最近记录：
13 年，5 月 前