包含特定顶点的最小循环算法

Question

我正在寻找一种算法，该算法可以找到包含给定顶点的非常基本(即最短)的循环。

换句话说，如果一个顶点 v1 参与两个循环，比如一个有 v1、v2、v3，另一个有 v1、v2、v4、v5、v6。我希望算法给我 v1、v2、v3 循环作为输出。

有谁知道哪种算法可以做到这一点？

此外，该算法的复杂性可能是什么。

提前致谢。

Answer 1

从给定的顶点 v0 开始一个 bfs。一旦 bfs 认为顶点 v1 与 v0 相邻，并且 v0 不是 bfs 树中 v1 的父节点，就立即停止。找到的从 v0 到 v1 加上 (v1,v0) 边的路径是你的最短周期。由于 bfs，复杂度为 O(n+m)。