algorithm - 设计一种算法来检测图 G 中的循环

Question

下面的算法会是什么样子:

线性时间算法，给定无向图 G 和其中的特定边 e，确定 G 是否有包含 e 的环

我有以下想法:

对于属于V的每个v，如果 v 是 e 的后代并且 (e,v) 还没有被遍历然后检查以下内容:

如果我们在 v 之前访问了 e 并且在我们离开 e 之前离开了 v 那么该图包含循环

Answer 1

我不确定这是否是你的作业，所以我只给出一点提示 - 使用广度优先搜索树的属性(根在边 e 的两个顶点中的任何一个)，它的子树是由根的邻居和这些子树之间的边决定。