トポロジカルソートは、私が私の脳でプログラムしたことを望むアルゴリズムです.非常に多くのタスクを毎日行うには、多くの依存関係で.それは確かに任意の外部ツールに依存することなく私の生産性を改善しているだろう.

免責事項
チキンBiryaniの例は、それを楽しい楽しみにするために選ばれます.私は、ステップを一般化して、詳細を取り除きました.ステップは、Googleが私に与えた最初のリンクから選ばれました.このレシピの複数のバリエーションがあります.あなたがBiryaniが何であるかについて、わからないならば、hereを訪問してください.あなたが若干のBiryaniを料理することに決めるならば、これはあなたが言及するべきでないポストです.私はあなたが漠然とした要件で開発を開始するときに何が起こるかを知っていると思いますか?
それでは、いくつかのチキンBiryani料理を始めましょう.

位相ソート

トポロジカルソートは、グラフ内の頂点の順序に使用されるアルゴリズムです.それは依存性に基づいて頂点の線形順序を出力します.依存関係をグラフのエッジとして表します.

は、方向を示すエッジを持っている有向非巡回グラフ(Dags)-グラフのみに動作します.頂点はそれらの間の一方向の関係を有する.また、頂点間の循環的依存性はないはずです.

コンピューターサイエンスの世界でこのアルゴリズムのいくつかの一般的なアプリケーションが含まれます

の仕事仕事スケジューリング

命令スケジューリング

メイキングファイルを通してコンパイルシーケンスを決定する

.

問題点:

我々がBiryaniを作っていたと仮定してください、そして、我々は誰かにそのレシピのステップの線形順序を教えて欲しいと思いました、一度に1ステップをとることによって続くことができるステップのシーケンス.Biryaniを作るときの手順は、他のレシピと同じように、それらの間の相互依存している.チキンバーヤニ(私が使用したリンクからの)の一般的なプロセスは、以下に概説されます

すべての必要な成分を購入する.

米を浸す.

チキンをマリネ.

は、層状、すなわち揚げたタマネギ、ミントの葉などを準備する

米を炊く.

コックチキン.

鶏にレイジングを加える.

米を上に乗せた.

サーブ!

この問題はとても些細なことですが、このアルゴリズムの現実世界のアプリケーションは何百ものステップ(頂点)とより複雑な依存関係を含むことができます.このポストの目的のために、私たちはそれを短く理解しやすいでしょう.

アルゴリズム

この問題にアプローチするために、複数のトポロジカルソーティングalgorithmsがある.これらのアルゴリズムのうちの1つはKahn's algorithmです.そして、それは私がこのポストで説明するのを選んだものです.
このアルゴリズムは以下の手順で動作します.

は、依存関係を持たない頂点、すなわち実行できる最初のタスクを見つける.

グラフから頂点を削除し、他の頂点がこのタスクに持っていた依存関係(エッジ)を削除します.この頂点を結果リストに追加します.

は、グラフの残りの部分の2ステップを繰り返します.

擬似コードは次のように書くことができます。

RS <- List to hold final ordered vertices
PQ <- A queue to hold vertices chosen for processing after 
they are removed from the graph

while PQ is not empty:
    -Current <- Dequeue a vertex from PQ
    -Add Current to RS
    for every vertex n dependent on Current:
        -Remove edge Current -> n
        -if n has no other incoming edge, enqueue it to PQ

if graph still has edges then
    return error (graph is not a DAG)
else
    return RS

これはBreadth First Searchアプローチを使用します.また、このアルゴリズムのDepth First Searchの変化もあります.
基本的に、ステップ' x 'に依存しているステップ' y 'がステップ' x 'の後に実行されることを確認して、このアルゴリズムの主なゴールです.
次に、私たちのBiryaniの問題を上記のアルゴリズムで解決することができます.手順をグラフ形式にしましょう.

私たちは他の何にも依存しない頂点から始めます.我々の場合では、それは'購入成分(BI)です.処理キューに追加し、ループを開始します.

我々は処理キューから最初の頂点を削除する.現在、' bi 'は我々の待ち行列に存在します.結果リストに追加します.

では、グラフから端部bi -> src、bi -> pl、bi -> mchを削除します.ここで、「エッジを取り除く」というのは、実際にはあなたの実装に依存します.私の実装(以下にリンク)では、各頂点' x 'の度合いカウンターを維持し、頂点' x 'の数を追跡します.また、「X」で隣接リストを維持し、次のステップを示す.頂点' v 'が結果リストに追加されるたびに、' V 'に依存した頂点の度合いは1で減らされます.

すべての3つの頂点(SRC、PL、MCH)のための

、Biは唯一の依存性でした.そのBIが結果に加えられる今、これらの3つの頂点は処理待ち行列に加えられます.

処理待ち行列が空であるまで、ステップの上の

は実行されます.

以上のグラフの処理を表の下に描いた.それが読むのが難しいならば、同じものは下でリンクされる倉庫でアップロードされました.

この問題の実装は以下のリポジトリにあります.

アンキテックテック / トポロジカル

トポロジカル

Biryaniを作る際のソートステップのためのC .これは私が書いたブログの補助的な実装です.
View on GitHub
トポロジカルソートアルゴリズムのコアは以下のファイルにあります.
< div >

トポロジカルソートに関するいくつかの事実

<ウル>

それは有向非巡回グラフ上でのみ動作します.グラフが周期を持っているなら、それは有効な位相ソートを持つことができません.

グラフは1つ以上の有効なトポロジカルソートを持つことができます.上の例では、頂点PL(準備段階)の前に頂点MCH(Malinate Chicken)を処理する場合、順序は少し異なっていました(そして、まだ有効です).

あらゆるDAGは、少なくとも一つの有効なトポロジカルソートを有する.

このアルゴリズムの時間複雑度は、O(＝v≧＋1)であるVは、グラフの頂点の数である.我々は、一度ごとに頂点を訪問しており、次第に計算してください.

< ull >
何か疑問があればpingをください.また、少なくとも一度はBiryaniを試してください!p >