方法: 1. グラフ内で入次数 0 のノードを見つけ、このノードをグラフから削除してシーケンス E に追加します; 2. 1 で見つかったすべてのノードを関連付けます。エッジは次のとおりです。グラフから削除; 3. グラフ内のすべてのノードが削除されるか、入次数が 0 のノードが見つからなくなるまで、ステップ 1 と 2 を繰り返します。
このチュートリアルの動作環境: Windows 7 システム、Dell G3 コンピューター。
グラフ内で内次数 0 のノードを見つけ、このノードをグラフから削除してシーケンスに追加します E
1 で見つかったノードに関連するすべてのエッジをグラフから削除します
グラフ内のすべてのノードが削除されるか、内次数が 0 のノードが見つからなくなるまで、1 と 2 を繰り返します。
この時点のグラフ内のノード数が 0 であれば、位相系列が見つかったことになります。この時点のグラフ内のノード数が 0 でなければ、これは、グラフ内に循環があり、トポロジカルソートが実行できないことを意味します。
拡張情報:
有向非巡回グラフ (略して DAG) G でトポロジカル ソートを実行するには、G 内のすべての頂点を次のような線形シーケンスに配置します。グラフ内の頂点 u と v の任意のペアについて、エッジ ∈E(G) の場合、線形シーケンスでは u が v の前に表示されます。通常、このような線形系列を位相順序を満たす系列、あるいはトポロジカル系列と呼ぶ。簡単に言うと、セットの部分順序からセットの全順序へのこの操作は、トポロジカル ソートと呼ばれます。
実行手順
AOV ネットワークからトポロジカル シーケンスを構築するトポロジカル ソート アルゴリズムは、主に次の 2 つのステップを、内次数が 0 の頂点がなくなるまでループで実行します。
(1) 内次数 0 の頂点を選択して出力します;
(2) この頂点とすべての出力エッジをネットワークから削除します。
ループ終了後、出力頂点の数がネットワーク内の頂点の数より少ない場合は、「ループ」情報が出力されます。それ以外の場合、出力頂点シーケンスはトポロジカル シーケンスになります。
コンピュータ関連の知識について詳しくは、FAQ 列をご覧ください。
以上がトポロジカルソートはどのようにソートされるのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。