トポロジカルソート: Python, C++ アルゴリズムの例

トポロジカルソートアルゴリズムとは何ですか?

トポロジカルソートはカーンのアルゴリズムとしても知られ、一般的なソートアルゴリズムです。トポロジカルソートは、有向グラフを入力として使用して、各ノードがそのノードが指すノードの前に表示されるようにノードを並べ替えます。

このアルゴリズムは DAG (有向非巡回グラフ) に適用され、各ノードが他のすべてのノードがポイントされる前に順序付けされた配列に表示されます。このアルゴリズムは、ソートが完了するまで、いくつかのルールに従います。

簡単に説明すると、次の例をご覧ください。

ここで、「A」には度数がないことがわかります。ノードを指すエッジを意味します。「B」と「C」には「A」という前提条件があり、次に「E」には「D」と「F」ノードという前提条件があります。一部のノードは他のノードに依存しています。

上記のグラフを別の形式で表現したものが次のとおりです。

したがって、DAG (有向非巡回グラフ) をトポロジカルソートに渡すと、最初の要素に依存関係がない線形順序の配列が得られます。

この例は、サイクルを含むグラフを示しています。

これを行う手順は次のとおりです。

ステップ1） 入力エッジがゼロのノード、つまり角度が XNUMX のノードを見つけます。

ステップ2） キューまたはスタック内の次数ノードをゼロにし、グラフからノードを削除するストア。

ステップ3） 次に、そのノードから発信エッジを削除します。

これにより、次のノードの次数カウントが減ります。

トポロジカルな順序付けでは、グラフデータ構造にサイクルがないことが必要です。

グラフが次の要件に従っている場合、グラフは DAG とみなされます。

indegree 値が XNUMX の XNUMX つ以上のノード。
グラフにはサイクルが含まれていません

グラフ内にノードがあり、グラフが DAG である限り、上記の 3 つの手順を実行します。そうでない場合、アルゴリズムは循環依存関係に陥り、カーンのアルゴリズムは入次数が 0 のノードを見つけることができません。

トポロジカルソートの仕組み

ここでは、トポロジカルソートに「カーンのアルゴリズム」を使用します。次のグラフがあるとします。

カーンのアルゴリズムの手順は次のとおりです。

ステップ1） グラフ内のすべてのノードの内次数または入力エッジを計算します。

ご注意:

Indegree は、ノードを指す有向エッジを意味します。
出次数とは、ノードからの有向エッジを意味します。

上記のグラフの入次数と出次数は次のとおりです。

ステップ2） ゼロの入次数またはゼロの入力エッジを持つノードを見つけます。

度数が XNUMX のノードは、そのノードに向かうエッジがないことを意味します。ノード「A」の度数は XNUMX です。これは、ノード「A」を指すエッジが存在しないことを意味します。

そこで、次のアクションを実行します。

このノードとその出次エッジ (外向きエッジ) を削除します。
ノードを注文用のキューに入れます。
「A」の隣接ノードの次数カウントを更新します。

ステップ3） indegree 値が XNUMX のノードを見つける必要があります。この例では、「B」と「C」の次数は XNUMX です。

ここでは、この XNUMX つのどちらかを選択できます。「B」をグラフから削除してみましょう。

次に、他のノードの度数値を更新します。

これらの操作を実行すると、グラフとキューは次のようになります。

ステップ4） ノード「C」には入力エッジがありません。そこで、グラフからノード「C」を削除し、キューにプッシュします。

「C」から出ているエッジを削除することもできます。

これで、グラフは次のようになります。

ステップ5） ノード「D」と「F」の次数が XNUMX であることがわかります。ノードを取得してキューに入れます。

まずは「D」を取り出してみましょう。この場合、ノード「E」の入次数は 1 になります。これで、D から E までのノードはなくなります。

ノード「F」に対しても同じことを行う必要があります。結果は次のようになります。

ステップ6） ノード「E」の入次数（入力エッジ）と出力次数（出力エッジ）がゼロになりました。したがって、ノード「E」の前提条件はすべて満たされています。

ここでは、キューの最後に「E」を付けます。したがって、ノードが残っていないため、アルゴリズムはここで終了します。

トポロジカルソートの疑似コード

以下は、カーンアルゴリズムを使用したトポロジカルソートの疑似コードです。

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  While node with O indegree present:
    topological_list.append(node)
    G.remove(node)
    Update Indegree of present nodes
  Return topological_list

トポロジカルソートは、DFS を使用して実装することもできます (深さ優先探索）方法。ただし、そのアプローチは再帰的方法です。カーンのアルゴリズムは、DFS アプローチよりも効率的です。

C++ トポロジカルソートの実装

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

出力

0       1       2       3       5       4

Python トポロジカルソートの実装

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list) 
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

出力

[0, 1, 2, 3, 5, 4]

トポロジカルソートアルゴリズムの循環グラフ

サイクルを含むグラフはトポロジー的に順序付けることができません。循環グラフは循環的に依存関係を持っています。

たとえば、次のグラフを確認してください。

A、B、C がサイクルを作成するため、このグラフは DAG (有向非巡回グラフ) ではありません。気が付けば、次数の値がゼロのノードは存在しません。

カーンのアルゴリズムによれば、上記のグラフを分析すると次のようになります。

入次数が XNUMX (入力エッジがない) のノードを見つけます。
そのノードをグラフから削除し、キューにプッシュします。
ただし、上記のグラフには、度が 0 のノードはありません。すべてのノードの次数の値は XNUMX より大きくなります。
度数が XNUMX のノードが見つからなかったため、空のキューを返します。

次の手順でトポロジカル順序付けを使用してサイクルを検出できます。

ステップ1） トポロジーソートを実行します。

ステップ2） トポロジー的にソートされたリスト内の要素の総数を計算します。

ステップ3） 要素の数が頂点の総数と等しい場合、循環は存在しません。

ステップ4） それが頂点の数と等しくない場合、指定されたグラフデータ構造には少なくとも XNUMX つのサイクルが存在します。

トポロジカルソートの複雑性分析

アルゴリズムの複雑さには2つの種類があります。

時間の複雑さ
スペースの複雑さ

これらの複雑さは、一般的な複雑さを提供する関数で表現されます。

時間計算量： トポロジカルソートでは、時間の計算量はすべて同じです。時間の計算量には、最悪、平均、最良のシナリオがあります。

トポロジカルソートの時間計算量は O(E + V) です。ここで、E はグラフ内のエッジの数、V はグラフ内の頂点の数を意味します。

この複雑さを打破しましょう:

ステップ1） 最初に、すべての入次数を計算します。これを行うには、すべてのエッジを通過する必要があり、最初にすべての V 頂点の度数を XNUMX に割り当てます。したがって、完了する段階的なステップは次のようになります。 O（V + E）.

ステップ2） 角度値が XNUMX のノードを見つけます。頂点の V 番号から検索する必要があります。したがって、完了した手順は次のようになります O（V）.

ステップ3） 入度がゼロのノードについては、そのノードを削除し、入度を減算します。この操作をすべてのノードに対して実行すると、 O(エ).

ステップ4） 最後に周期があるかどうかを確認します。ソートされた配列内の要素の合計数がノードの合計数と等しいかどうかを確認します。かかる O（1）.

したがって、これらはトポロジカルソートまたはトポロジカル順序付けの各ステップの個別の時間計算量です。上記の計算から、時間計算量は O( V + E ) になると言えます。ここで、O は計算量関数を意味します。

スペースの複雑さ： トポロジカルソートアルゴリズムを実行するには O(V) スペースが必要でした。

プログラム用のスペースが必要な手順は次のとおりです。

グラフ内に存在するノードのすべての入次数を計算する必要がありました。グラフには合計 V 個のノードがあるため、サイズ V の配列を作成する必要があります。したがって、必要なスペースは次のとおりです。 O（V）.
Queue データ構造は、ゼロ度数のノードを格納するために使用されました。元のグラフから次数ゼロのノードを削除し、キューに配置しました。このために必要なスペースは、 O（V）.
配列の名前は「order」です。これにより、ノードがトポロジ順に保存されました。それも必要でした O（V） スペース

これらは個々のスペースの複雑さです。したがって、実行時にこれらのスペースを最大化する必要があります。

空間計算量は O(V) を表します。ここで、V はグラフ内の頂点の数を意味します。

トポロジカルソートの応用

トポロジカルソートには非常に便利な用途があります。その一部を次に示します。

というときに使われます。 Operaティンシステムリソース割り当てを実行する必要があります。
グラフ内のサイクルを見つける。トポロジカルソートを使用して、グラフが DAG であるかどうかを検証できます。
オートコンプリートアプリでの文章の順序付け。
を検出するために使用されますデッドロック.
さまざまなタイプのスケジューリングまたはコーススケジューリングでは、トポロジカルソートが使用されます。
依存関係の解決。たとえば、パッケージをインストールしようとすると、そのパッケージには他のパッケージも必要になる可能性があります。トポロジカルな順序付けにより、現在のパッケージをインストールするために必要なすべてのパッケージが検索されます。
Linux 「apt」のトポロジーソートを使用してパッケージの依存関係をチェックします。

よろしければ：