确定边是否属于某个循环的高效算法
Efficient algorithm that decides if an edge belongs to some cycle
我正在尝试构建一个有效的算法来获取无向图和边 e(u,v)，并确定边是否属于图中的某个循环，但不是所有循环！
我的做法是从图中取出边(u,v)，然后运行 BFS看v是否仍然可以从u到达。如果是，则原始图有一个包含 e 的循环，否则没有。
但是我不太确定如何调整算法以决定边缘是否不属于图形的所有循环。
无向图可以包含属于其所有循环图的边，前提是该图只有一个循环。
我们来看一个例子。边(2,3)属于两个循环，但你总能找到这样一条边不属于的第三个循环。
检查该边属于某个环后，您可以通过删除该边并检查缩减图是否有任何环来检查这是否是图中唯一的环。感谢@nomanpouigt 指出这一点。
我正在尝试构建一个有效的算法来获取无向图和边 e(u,v)，并确定边是否属于图中的某个循环，但不是所有循环！ 我的做法是从图中取出边(u,v)，然后运行 BFS看v是否仍然可以从u到达。如果是，则原始图有一个包含 e 的循环，否则没有。 但是我不太确定如何调整算法以决定边缘是否不属于图形的所有循环。
无向图可以包含属于其所有循环图的边，前提是该图只有一个循环。
我们来看一个例子。边(2,3)属于两个循环，但你总能找到这样一条边不属于的第三个循环。
检查该边属于某个环后，您可以通过删除该边并检查缩减图是否有任何环来检查这是否是图中唯一的环。感谢@nomanpouigt 指出这一点。