エッジがあるサイクルにあるかどうかをチェックする方法？

Question

私は任意のエッジ 'E'を含む任意の無向グラフにサイクルが存在するかどうかを検出するアルゴリズムを求めています。アルゴリズムはO（N）線形時間で実行する必要があります。

私が持っている問題は、どこから始めるべきか分かりません。私はいくつかの簡単なサンプルグラフを持っていますが、そこからどこに行くのか分かりません。

ヒント

Answer 1

エッジ「e」から始めます。そこから、接続する2つの頂点を取得する必要があります。それらからあなたは他の辺や他の頂点、他の辺や他の頂点を得ます。あなたのアルゴリズムによって頂点が既に「訪問された」かどうかを判断する方法が必要です。それがある場合、 'e'が含まれているサイクルがあります。

Answer 2

あなたが行くにつれてノードをリストに追加し、返されるときにそれらをリストから削除します。

リストは、現在のトラバーサルパスを表します。

すでにリストに入っているノードを見つけたら、ループ/サイクルがあります。エッジについて

Answer 3

（U、V）：

1-、Uから出発して深さ優先検索を実行Vが検出されたかどうかを決定し、バックエッジがVへのパスに沿って存在する

-2-。 Uに存在し、その後、UおよびVの両方を含むサイクルがありますUが見つかり、バックされた場合、エッジ、Vから深さ優先検索を実行する。すなわち

を

1- Uから出発してDFSを実行しますバックエッジが存在し、vがまだ終了していないかどうかを確認します。

2νから始まるDFSを実行し、両方の条件が真でエッジU、Vが1つのサイクルに属している場合は、バックエッジが存在し、uが終了していないかどうかを確認します。

Answer 4

Gのからそのエッジ（u、v）を取り出します。1. BFSを実行して、vがまだuから到達可能かどうかを確認します。 2.はいの場合、元のグラフはeを含むサイクルになります。それ以外の場合はありません。