我研究了有向图中循环检测算法的各种算法,如增量方式搜索、强连接组件、BFS、双向搜索等。现在我想模拟它并比较性能。每当我插入边时,我都会调用循环检测函数。
所以,我的问题是我应该考虑什么样的数据集。如果我考虑随机图,那么评估各种算法的标准应该是什么。一些随机图可能很大;但它们可能会在几次迭代中导致循环。如果有人可以建议如何解决这个问题,那将会很有帮助。
此外,为了比较性能,删除循环然后再次继续插入是否有意义。一旦它终止,比较所有实现的执行时间?
最佳答案
这实际上取决于您这样做的目的。一般来说,有很多随机图生成方法,但可以说最著名的是Erdos-Renyi。 .但是请注意,对于具有 n 个顶点的图没有循环,它必须最多有 n - 1 条边,因此这样的随机图生成器将有很大概率有循环。根据您的具体情况,您可能会发现最好使图形尽可能稀疏(即允许很少的边)。
关于algorithm - 如何通过实验模拟和比较各种图循环检测算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38401154/