我有一个有向图，有562个顶点和3961条边(如果你好奇的话，这些边是http://a3nm.net/share/raw_graph_284374.txt)，我想在这个图中找到一个循环，它不会经过两次相同的顶点，并且尽可能长。
我知道这个问题是np困难的(通过哈密顿循环问题的简化)，但我并不真正关心找到最长的循环，只是一个合理的长循环。一个简单的DFS实现可以找到长度为100-200的周期，但我确信有许多启发式和改进可以用来找到更长的周期。
是否有任何(开源)程序或库，我可以用它来找到一个更长的周期在这个大小的图?
我想你可以简化你的问题。注意，当一个循环失去一条边时，它会变成一条路径。基本上，你可以这样做
1)考虑每对节点u,v
2)移除两个节点之间的边。
3)找到最长路径(或近似最长路径)https://en.wikipedia.org/wiki/Longest_path_problem
4)移除的边缘和路径的组合将为您提供一个长周期。
我认为如果你尝试用BFS使你的图成为DAG(有向无环图)，那么你可以在线性时间和精确(没有近似)下解决最长路径的问题。