スパニングツリーとスパニングツリー上にないエッジがある場合、サイクルベースを形成する方法は？

Question

エッジEおよび頂点Vのグラフがあり、クラスカルアルゴリズム（またはその他のあらゆるトラバースバックトラックトラバースアゲインアルゴリズム）、ここで、そのスパニングツリーとエッジ上にないエッジを利用して作成されたすべてのサイクルベースを検索したいツリー、ブルートフォース検索に加えて、それを可能にするアルゴリズムはありますか？

もちろん、非スパンツリーエッジの1つの頂点から開始し、すべてのエッジを取得し、それらすべてを探索し、行き止まりを見つけた場合は、エッジのもう1つの頂点に戻るまで格納します。しかし、これは少し、エラーです...残忍です。他のアイデアはありますか？

Answer 1

グラフ内のサイクルを見つけるために使用する単純なアルゴリズム：

  

深さ優先のスパニングツリーを作成する   各ノードには親があります。       ツリーを走査する際に、使用済みノードのレコードを作成します。       エッジが以前に使用されたノードを指す場合、それを   サイクリックエッジ。       スパニングツリーが完了すると、巡回のカウント   エッジはサイクル数を示します。       2つのノードの先祖を巡回する各循環エッジについて   共通の祖先が見つかるまで。それ   サイクルを正確に示します。

共通の祖先をすばやく見つけることができるように、循環エッジノードのすべての祖先のインデックス（ハッシュテーブル）があると便利です。

これが最良のアルゴリズムであるとは思わないが、かなり速い。

コメントするには、

編集 スパニングツリーの各ノードには親があります。巡回エッジのノードに到達すると、祖先のリストを計算します(List<Node>このリストは速度のためにインデックス付けできます（つまり、contains（）は< O(n))です。2つのノード（n1, n2）を持つ巡回エッジが見つかった場合n1, n1.ancestorListの祖先を反復処理し（リストがすでに作成されているため、急速に）、祖先がn2.ancestorListにあるかどうかをテストします。 commonAncestor（高速）に到達するまでのn2時間は、リスト内のルックアップと組み合わせたサイクリックエッジの数に依存する必要があります（おそらくO(logN)が安価）。グラフを再探索する必要はなく、バックトラッキングなし。

Answer 2

スパニングツリーを構築した後、ツリー内にないすべてのエッジ（A、B）で反復し、このエッジのノードの最小共通祖先（LCA）を見つけると、サイクルは次のパスになります。 A-<！> gt; LCA-<！> gt; B-<！> gt; A

このリンクを使用できます： http：//www.topcoder .com / tc？module = Static <！> amp; d1 = tutorials <！> amp; d2 = lowestCommonAncestor     効率的な最小共通祖先アルゴリズムの実装のため。