4

我有一个有 562 个顶点和 3961 个边的有向图（如果你好奇，边是http://a3nm.net/share/raw_graph_284374.txt），我想在这个图中找到一个不会经过两次的循环相同的顶点并且尽可能长。

我知道这个问题是 NP 难的（通过减少哈密顿循环问题），但我并不真正关心找到最长的循环，只是一个相当长的循环。一个简单的 DFS 实现可以找到长度为 100-200 的循环，但我确信有许多启发式方法和改进可以用来找到更长的循环。

是否有任何（开源）程序或库可用于在这种大小的图中找到更长的周期？

4

1 回答 1

0

我认为你可以简化你的问题。请注意，当一个循环失去一条边时，它会变成一条路径。因此，基本上，您可以执行以下操作

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

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

3）找到最长的路径（或近似最长的路径）https://en.wikipedia.org/wiki/Longest_path_problem

4）去除的边缘和路径的组合将为您提供一个很长的周期。

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

于 2016-04-24T19:45:12.993 回答