6

始める前に、はい、これは宿題です。過去 14 時間、この問題を解決するためにできる限りの努力をしなければ、ここに投稿することはなかったでしょう。

問題は次のとおりです。線形だけでなく、O(V)時間で、接続された無向グラフからエッジを切断せずに削除できるかどうかを確認したい。

私がこれまでに到達したこと：

グラフを切断せずにサイクル エッジを削除できるので、グラフにサイクルがあるかどうかを確認するだけです。使用できる方法は 2 つあります。1 つは DFS で、バック エッジがあるかどうかを確認します。もう 1 つは、Vs と Es をカウントし、|E| かどうかをチェックすることです。= |V| - 1、それが true の場合、グラフはツリーであり、切断せずに削除できるノードはありません。

前のアプローチはどちらも問題を解決しますが、どちらも O(|E|+|V|) を必要とし、本にはもっと速い方法があると書かれています (それはおそらく貪欲なアプローチです)。

ヒントをいただけますか？

編集:より具体的には、これは私の質問です。接続されたグラフ G=(V,E) が与えられた場合、E の一部のエッジ e を削除して、結果のグラフを接続したままにすることはできますか?

4

4 に答える 4

9

グラフを再帰的にトラバースし、ノードにアクセスしたときにノードをマークし、すでにマークされているノードに遭遇した場合にtrueを返すように短絡すると、うまくいきます。これにより、削除できるエッジがない場合はO（| V |）がグラフ全体をトラバースし、trueに戻るために早期に停止した場合は時間が短縮されます。

編集

はい、グラフ全体の再帰的トラバースにはO（| V | + | E |）時間が必要ですが、サイクルがない場合にのみグラフ全体をトラバースします。この場合、| E | = | V | -1であり、O（| V |）時間しかかかりません。サイクルがある場合、最大で|V|をトラバースした後にそれを見つけます。エッジ（および最大で| V | +1ノードを訪問）。これには同様にO（| V |）時間がかかります。

また、明らかに、ノード（最初のノード以外）からトラバースする場合、ノードに到達するために使用したエッジは考慮されません。これにより、既にアクセスされたノードがすぐに表示されます。

于 2012-01-03T02:47:07.263 に答える
-1

私が読んでいることから、繰り返しのない DFS は O(|V|) と見なされるため、エッジ e を取り、それが接続する 2 つの頂点を u と v とすると、e を無視して u から DFS を実行すると、次のことができます。 v が発見された場合、e はブリッジではないと推測し、繰り返しのない DFS が O(|V|) であるとすると、これは O(|V|) と見なされると思います。

于 2012-01-03T02:30:07.757 に答える