1. 序章

このチュートリアルでは、有向グラフでPrimeおよびKruskalのアルゴリズムを使用できない理由を探ります。

2. 最小スパニングツリー

両方のアルゴリズムは、無向グラフで最小スパニングツリーを見つけるために使用されます。 最小全域木（MST）は、グラフのサブグラフです。 このサブグラフには、重みが最も少ないエッジが含まれ、同時に元のグラフのすべてのノードが含まれています。

 

示されているグラフは、重みが9の最小全域木を視覚化したものです。

2.1. クラスカルのアルゴリズム

クラスカルのアルゴリズムが機能するには、無向、加重、接続されたグラフが必要です。 そのアイデアは非常に単純です：

  • データ構造を作成します。
  • 作成されたグラフに回路が含まれないように、重みが最も小さいエッジをデータ構造に追加します。
  • スパニングツリーが形成されるまで、これらの手順を続けます。

ここで、有向グラフのように、円を正しく検出しないと問題が発生する可能性があることにすでに気付くことができます。

2.2. プリムのアルゴリズム

Primのアルゴリズムは、ランダムノードから開始し、グラフをトラバースして、重みが最も低いエッジを選択することで機能します。この方法は、ダイクストラのアルゴリズムを思い出させますが、実際には、エッジの直接の重みのみを優先し、パス全体を優先しません。ダイクストラなどの開始ノード。

詳細については、擬似コードを見てみましょう。

2.3. 比較

2つのアルゴリズムをすばやく比較するために、クラスカルのアルゴリズムはまばらなグラフで非常にうまく機能し、実装が簡単であると結論付けます。一方、プリムのアルゴリズムは、エッジの多いグラフでは高速ですが、より困難です。実装する。

3. 問題のあるインスタンス

アルゴリズムの分析ですでに見たように、両方とも無向グラフを必要とします。 有向グラフを入力してもアルゴリズムが自動的に停止するわけではありませんが、いくつかの例で、有向グラフ自体を許可できない理由を示すことができます。

3.1. 樹枝状の問題

有向グラフには最小スパニングツリーの古典的な概念がないため、最小スパニングアーボレッセンス（MSA）を使用します。 最小スパン樹木は有向ツリーです。 グラフ内の他のすべてのノードへのパスが存在する1つのノードが含まれています：

 

3.1. クラスカル

クラスカルアルゴリズムの反例：

 

この例では、可能なMSAは1つだけです。 あれは 。 しかし、クラスカルのアルゴリズムを実行して、まず最初に以下を選択します。

 

このエッジはMSAに含まれていないため、この例ではクラスカルアルゴリズムからエッジを構築することはできません。

3.2. 堅苦しい

プリムアルゴリズムについても、同様の設定があります。

 

今回は、可能なMSAはです。 プリムのアルゴリズムは、ランダムノード（この場合は）から始まります。 次に、最も低いエッジがに接続されているエッジを取得します。これは、次のノードです。

 

エッジは、次の手順でこの例のMSAが生成されない唯一のMSAには含まれていません。

4. Chu–Liu/Edmondsのアルゴリズム

Chiu-Liu / Edmondsのアルゴリズムは、有向接続グラフのMSA問題を解決できる代替手段です。 それが機能するためには、MSAのルートとして機能するすでに選択されたノードrが必要です。 アルゴリズムは、サイクルを排除することにより、グラフを再帰的にMSAに変換します。

4.1. 概要

Chiu-Liuアルゴリズムを次のフローチャートで説明します。

 

まず、MSAのルートには入力エッジがないため、ルートにつながるすべてのエッジを削除します。 次に、グラフ内の各ノードを見て、そのソースをで示す、最も低い入力エッジeを選択します。 次に、MSAがすでにあるかどうかを確認します。 そうでない場合は、グラフのサイクルを再帰的に削除します。

4.2. サイクルの排除

より良い視点を得るために、サイクルを単一のノードに変換するステップをもう一度見てみましょう。

にあるノードとないすべてのノードについて、新しい重み関数を使用してセットを作成します。 のノードに接続するすべてのエッジについて、次のルールを実行し、新しいエッジのセットを作成します。

1. のエッジの場合、で新しいエッジを作成し、を定義します。 2. のエッジの場合、で新しいエッジを作成し、を定義します。 3. 円にノードが含まれていないすべてのエッジについて、元のグラフのエッジとエッジの重みを保持します。

サイクルを含まないグラフができるまで、この削減を行います。 構築されたものにはサイクルがないため、MSAがあります。 これで、元のノードがすべて含まれるグラフに変換し直すだけで済みます。

このために、構築されたノードを見てみましょう。これらのノードには、入力エッジが1つだけあります。 このエッジは、元のグラフのエッジに対応し、vはサイクル内にあります。

次に、元のグラフからを削除して、サイクルを中断します。

構築されたすべてのノードに対してこれを続けて行うと、すべての元のノードを含み、サイクルフリーのグラフになります。このグラフは、MSA問題の解決策です。

4.3. 複雑

最悪の場合、グラフ内のすべてのノードをチェックします。 また、ノードごとに、グラフのすべてのエッジの重みを変更する必要があります。 したがって、時間計算量は次のようになります。フィボナッチヒープなどのフィッティングデータ構造を使用すると、複雑さを次のように減らすことができます。

5. 結論

この記事では、クラスカルアルゴリズムもプリムアルゴリズムも有向グラフに適用できない理由について説明しました。 さらに、特定の有向グラフとルートノードの最小スパンアーボレッセンスを取得する代替案を検討しました。