我正在寻找一个算法，找到所有循环的所有边的总权重大于0。我听说这个问题是np完全的，但是由于我想为一个总是看起来或多或少相同的特殊图解决这个问题，我希望有一个更简单的方法。
我的图表如下：
它始终是所有水平和垂直相邻顶点之间的n * n顶点和边的平方。只有两种可能的权重，黑边为-1，绿边为+1。
在这个例子中，我要寻找的循环是：
7；12；17；18；19；14；13；8；7=>重量：+1
7；12；13；8；7=>重量：+1
7；8；7=>重量：+2
18；23；24；19；18=>重量：+1
7；12；17；18；23；24；19；14；13；8；7重量：=>+2
对于这个任务，什么样的算法是有效的？它应该很快，因为我还想对顶点n = 25 => 625的图执行此操作。
最佳答案
为什么不将基本循环检测与dfs一起使用并对其进行一些修改：
当你遇到一个节点时，如果你已经访问了同一个节点，你知道你在一个循环中，所以你要检查权重是否为正，如果是的话，只要再循环一次，把路径保存在内存中。
如果你要访问的节点已经被看到，就停在这里。
然后递归地访问节点的邻居。
伪代码可能如下所示：
dfs(node, weight):
if state[node] is "in progress" AND weight > 0
// This is a cycle we want
Keep in memory the path (just go throught the cycle once more)
if state[node] is "visited"
Stop
state[node] = "in progress"
For each neighbour
dfs(neighbour, weight + edge_weight)
state[node] = "visited"
如果你为每个起始节点这样做，你应该得到一个时间复杂度大约为O（n*m）的n个顶点和m个边数。
希望这有帮助！
编辑：忘记更新状态
关于algorithm - 在特殊的有向图中找到重量> 0的所有循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35417050/