algorithm - 特定の頂点を含む最小サイクルへのアルゴリズム

Question

特定の頂点を含む非常に基本的な (つまり、最短の) サイクルを見つけることができるアルゴリズムを探していました。

言い換えると、頂点 v1 が 2 つのサイクルに参加する場合、1 つは v1、v2、v3 で、もう 1 つは 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) です。