我们给出一个简单的无向图G=(V,E)和V的子集S。
我们被告知，S 的所有顶点都在 G 中形成一个简单的循环(长度 |S|)。
现在，我们要找到精确的循环(或其任何循环移位)(S 的所有顶点的序列)。我们怎样才能找到它？有什么办法吗？
我尝试了DFS/BFS，但它似乎工作不正常。
例如:如果 G 中有 4 个顶点 A、B、C、D，边为 (A,C)、(A,D)、(B,C) ，(B，D)。令给定 S= {A, B, C, D}
那么我们的答案应该是ADBCA(或BCADB或其任何循环移位)。
最佳答案
首先，你需要迭代S中的所有节点。如果有任何节点的顶点少于两个，那么你将找不到这样的循环。然后，您需要生成包含所有节点的回溯路径，检查每个节点的最后一个节点和第一个节点之间是否存在顶点。如果你找到了这样一条路径，那么你就找到了这样一个循环。如果不是，则您使用的节点集中不存在这样的循环。
关于graph-theory - 寻找图中的循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35687499/