我研究了有向图中循环检测算法的各种算法，如增量方式搜索，强连通组件，BFS，双向搜索等 . 现在我想模拟它并比较性能 . 每当我插入边缘时，我都在调用循环检测功能 .
所以，我的问题是我应该考虑什么样的数据集 . 如果我考虑随机图，那么评估各种算法的标准应该是什么 . 一些随机图可能是巨大的;但它们可能导致几次迭代循环 . 如果有人可以建议如何解决这个问题会很有帮助 .
此外，为了比较性能，删除循环然后再次继续插入是否有意义 . 一旦它终止，比较所有实现的执行时间？
这真的取决于你为此做了什么 . 一般来说，有许多随机图生成方法，但可以说最着名的是Erdos-Renyi . 但请注意，对于n个顶点不具有循环的图形，它必须最多具有n-1个边缘，因此这样的随机图形生成器将具有高概率的循环 . 根据您的具体情况，您可能会发现最好尽可能保持图表稀疏（即允许少量边缘） .
1 回答
这真的取决于你为此做了什么 . 一般来说，有许多随机图生成方法，但可以说最着名的是Erdos-Renyi . 但请注意，对于n个顶点不具有循环的图形，它必须最多具有n-1个边缘，因此这样的随机图形生成器将具有高概率的循环 . 根据您的具体情况，您可能会发现最好尽可能保持图表稀疏（即允许少量边缘） .