在图中找到一个长的顶点不相交的环

Question

4

我有一个有向图，包含562个顶点和3961条边（如果您感兴趣，这些边的链接是http://a3nm.net/share/raw_graph_284374.txt），我想在这个图中找到一个不重复经过同一顶点且最长的环。

我知道这个问题是NP-hard的（通过从哈密尔顿回路问题进行约简），但我并不真正关心找到“最长”的循环，只是一个相当长的循环。一个朴素的DFS实现可以找到长度为100-200的循环，但我相信有许多启发式和改进可以用来找到更长的循环。

是否有任何（开源）程序或库可用于在这么大的图中找到更长的循环？

- a3nm

我没有什么好的答案建议，但是你链接的数据集有562个顶点和3961条边。我的深度优先搜索尝试在这里找到大约200个顶点的循环（每次不同，因为我会随机改变考虑边的顺序）。 - Sumudu Fernando

哦，抱歉，我在对错误的文件进行测试。我已相应地编辑了问题。感谢您指出！ - a3nm

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- A. Mashreghi · Answer 1

我认为你可以简化你的问题。请注意，当一个环失去一条边时，它会变成一条路径。因此，你可以按照以下步骤进行：

1）考虑每对节点u,v。

2）删除两个节点之间的边缘。

4）被删除的边和路径的组合将为您提供一个长的循环。

我认为，如果你尝试使用BFS使你的图形成为DAG（有向无环图），那么你可以在线性时间内解决最长路径问题，并且是精确的（没有近似值）。