トポロジカルソートはどのようにソートされるのでしょうか?

方法: 1. グラフ内で入次数 0 のノードを見つけ、このノードをグラフから削除してシーケンス E に追加します; 2. 1 で見つかったすべてのノードを関連付けます。エッジは次のとおりです。グラフから削除; 3. グラフ内のすべてのノードが削除されるか、入次数が 0 のノードが見つからなくなるまで、ステップ 1 と 2 を繰り返します。

このチュートリアルの動作環境: Windows 7 システム、Dell G3 コンピューター。

1. グラフ内で内次数 0 のノードを見つけ、このノードをグラフから削除してシーケンスに追加します E

2. 1 で見つかったノードに関連するすべてのエッジをグラフから削除します

3. グラフ内のすべてのノードが削除されるか、内次数が 0 のノードが見つからなくなるまで、1 と 2 を繰り返します。

この時点のグラフ内のノード数が 0 であれば、位相系列が見つかったことになります。この時点のグラフ内のノード数が 0 でなければ、これは、グラフ内に循環があり、トポロジカルソートが実行できないことを意味します。

拡張情報:

有向非巡回グラフ (略して DAG) G でトポロジカル ソートを実行するには、G 内のすべての頂点を次のような線形シーケンスに配置します。グラフ内の頂点 u と v の任意のペアについて、エッジ ∈E(G) の場合、線形シーケンスでは u が v の前に表示されます。通常、このような線形系列を位相順序を満たす系列、あるいはトポロジカル系列と呼ぶ。簡単に言うと、セットの部分順序からセットの全順序へのこの操作は、トポロジカル ソートと呼ばれます。

実行手順

AOV ネットワークからトポロジカル シーケンスを構築するトポロジカル ソート アルゴリズムは、主に次の 2 つのステップを、内次数が 0 の頂点がなくなるまでループで実行します。

(1) 内次数 0 の頂点を選択して出力します;

(2) この頂点とすべての出力エッジをネットワークから削除します。

ループ終了後、出力頂点の数がネットワーク内の頂点の数より少ない場合は、「ループ」情報が出力されます。それ以外の場合、出力頂点シーケンスはトポロジカル シーケンスになります。

コンピュータ関連の知識について詳しくは、FAQ 列をご覧ください。

以上がトポロジカルソートはどのようにソートされるのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。