無向グラフにサイクルが存在するかどうかを検出します。

Question

周期が存在する場合、私の質問はDETECTINGに関係します。私はサイクルがどこにあるかに関わらず、サイクルが存在する場合にのみ気にします。 特に、私は（最大限に）スパニングツリーアルゴリズムの実装に取り​​組んでいます。私は降順でエッジをソートし、その時に1つのエッジを選んでグラフのエッジのセットに入れてください。それはサイクルを引き起こさないIFFです。

無指向性グラフの場合、no_of_edges> no_of_vertices - 1であるかどうかをチェックするだけです。これは正しいですか？私はこれが真実でない場合を見つけようとしています。私はできません。もちろんこれはこれが正しいことを意味するものではありません。

おかげ

グラフが切断され、または複数のエッジが与えられた二つのノードの間にある場合

Answer 1

DFS検索を実行するだけです。それは自動的にループを検出します。これはDFSの停止条件です。すでにスタックに入っているノードを入力すると停止し、サイクルが見つかった時点で停止します。

Answer 2

、その後、あなたのアイデアが失敗します。任意の2つのノードの間に最大で1つのエッジがあると規定している場合は、引き続き接続性をチェックする必要があります。

ただし、接続されたグラフの辺の数が< =頂点の数-1の場合、サイクルはありません。

Answer 3

基本的にあなたの考えは正しいです。しかし、いくつかの落とし穴があるかもしれません。

1）まず、DFSを実行し、すべての接続されたコンポーネントを見つけ、条件no_of_edges < = no_of_verticesかどうかをチェック - 接続されているすべてのコンポーネントで1。

2）接続されている各コンポーネントに複数のエッジが含まれているかどうかを確認します。