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

Question

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

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

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

此外，该算法的复杂性可能是多少。

提前致谢。

Answer 1

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