7

有向グラフのすべての根を O(n+m) で見つけるアルゴリズムを見つける必要があります。

単一のルートを見つけるためのアルゴリズムがあります。

  1. V の一部の v に対して DFS(v) を実行します。結果が単一のスパニング ツリーである場合、v はルートです。それ以外の場合、結果は木の森になります。それで：
  2. 最後のツリーのルートで DFS(u) を実行します。結果が単一のスパニング ツリーの場合、u はルートです。そうでなければ、グラフに根はありません。

すべてのルートを見つけたい場合、毎回最後のツリーの異なる頂点で上記のアルゴリズムを O(n) 回実行するのが最善の方法ですか? ルートが見つかったと仮定すると、別のルートが存在する場合、それは最後のツリーにある必要があります。「ルートが存在しない」を受け取るまで、またはすべての頂点を通過するまで上記のアルゴリズムを実行し続けると、それは O(n+m) になりますか?

前もって感謝します ！

4

2 に答える 2

5

2 つのアプローチ:

  1. グラフを逆にして DFS-loop() を計算し、出辺がない頂点に注意してください (Abhishek が言ったように)。

  2. より効率的 - グラフで DFS-loop() を実行し、true, false テーブルを使用して着信エッジのない頂点を追跡します。

方法 1 は、最悪の場合、2 倍の時間がかかります。

于 2013-11-13T12:49:48.670 に答える
2

まず、グラフ内の強連結成分をすべて見つける必要があります。無駄のない時間で構築するには、Kosaraju のアルゴリズムまたはTarjan のアルゴリズムを使用できます。すべてのルートは、そのような 1 つのコンポーネントに配置する必要があります。次に、入力エッジのない強く接続されたコンポーネントを見つけます。そのようなコンポーネントが複数ある場合、グラフにはルート頂点がありません。コンポーネントが 1 つしかない場合は、そこから他のコンポーネントにアクセスできることを確認する必要があります。この場合、このコンポーネントにはグラフのすべてのルートが含まれます。

古いバリアント。

頂点への着信エッジの数を計算する必要があります。これは O(m) で実行できます。入力エッジの数がゼロのすべての頂点はグラフのルートになります。これには O(n) 時間が必要です。

于 2013-11-13T09:47:46.163 に答える