有向非巡回グラフ(DAG)におけるトポロジカルソーティング

トポロジーソートとは何か
それはDAGの頂点の順序です、あらゆるUのために、u、v、uはVの前に来ます.
重要な注意点
1)周期が1サイクルであればトポロジカルソートを行うことはできません.周期では頂点の順序を知ることができないので
2)トポロジカルソートの多くの可能な順序がある
例

可能なトポロジー順序:
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]
[ 3 , 2 , 1 , 4 , 5 , 6 , 7 , 8 ]
[ 1 , 2 , 3 , 4 , 7 , 6 , 5 , 8 ]

位相ソートの利用
1)タスクAが完了した場合にタスクBが完了することができると仮定します.グラフは次のようになります.
A -> B
そして、トポロジカル順序は[ A , B ]でしょう.
2)コースの管理と必須コース、例えば、基本的な数学(BM)コースの前提条件がある代数(AL)コースを持っている場合、グラフは次のようになります.
BMの
そして、トポロジの順序は、学生がALコースを取る前にBMコースを完了するべきであることを意味する[ BM , AL ]です.

アルゴリズム
我々は、我々が訪問した頂点と注文を保存するためにスタックを保存するためにハッシュセットを必要とします.
1 )頂点( v )をグラフから現在の頂点とします.
2 )現在の頂点がハッシュ集合でない場合

現在の頂点をハッシュセット

に追加します

現在の頂点のすべての子を取得し、それぞれの子頂点

に対してステップ2を再帰的に呼び出す

現在の頂点をスタック

に追加します
3 )スタックを反転させ、トポロジー順を得る

コード

    def topological_sort(self, graph, seen, stk, current_vertex):
        # 2) if current_vertex not in hash set
        if current_vertex not in seen:
            seen.add(current_vertex)
            current_vertex_children = graph[current_vertex]
            for child in current_vertex_children:
                self.topological_sort(graph, seen, stk, child)
            stk.append(current_vertex)


    # *** Main function ***
    def topoSort(self, v, graph):
        # v = no of vertices in the graph
        # graph is represented using an adjacency list
        stk = []
        seen = set()
        # 1) pick a vertex
        for vertex in range(v):
            self.topological_sort(graph, seen, stk, vertex)
        # 3) reverse the stk
        stk.reverse()
        return stk

トポロジカルソートによる問題解決
DAGのためのトポロジカルソートの実装
位相順のコース順:geeks-for-geeks-problem-link
すべてのコースが完了するかどうかチェックしてください