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

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

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

このアルゴリズムはDAG（有向非巡回グラフ）に適用され、各ノードが、それが指す他のすべてのノードよりも前に、順序付けられた配列に表示されるようにします。このアルゴリズムは、ソートが完了するまで、いくつかのルールを繰り返し実行します。

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

有向グラフ

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

上記グラフの別の表現を以下に示します。

各ノードの依存関係（線形順序付け）

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

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

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

ステップ2） 入次数がゼロのノードをキューまたはスタックに格納し、グラフからそのノードを削除します。

ステップ3） 次に、そのノードから出ているエッジを削除します。これにより、次のノードの入次数が減少します。

トポロジカル順序付けでは、グラフデータ構造にサイクルがあってはならない。グラフがDAG（有向非巡回グラフ）とみなされるのは、以下の要件を満たす場合である。

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

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

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

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

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

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

注意：

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

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

ステップ2） 入次数がゼロ、つまり入ってくるエッジがゼロのノードを探します。入次数がゼロのノードとは、そのノードに向かってくるエッジがないことを意味します。ノード「A」の入次数はゼロなので、ノード「A」に向かうエッジはありません。そこで、以下の操作を行います。

• このノードとその出次数エッジ（発信エッジ）を削除します。
• ノードを注文用のキューに入れます。
• 「A」の隣接ノードの入次数を更新します。

ステップ3） 入次数がゼロのノードを見つける必要があります。この例では、「B」と「C」の入次数はゼロです。ここでは、どちらか一方を選択できます。「B」を選択してグラフから削除します。次に、他のノードの入次数を更新します。これらの操作を実行すると、グラフとキューは次のようになります。

ステップ4） ノード「C」には入力エッジがありません。そのため、ノード「C」をグラフから削除し、キューに追加します。また、「C」から出ているエッジも削除できます。これで、グラフは次のようになります。

ステップ5） ノード「D」と「F」の入次数がゼロであることがわかります。ノードを1つ取り出してキューに入れます。まず「D」を取り出しましょう。すると、ノード「E」の入次数は1になります。これで、DからEへのノードはなくなります。ノード「F」についても同じ操作を行うと、結果は次のようになります。

ステップ6） ノード「E」の入次数（入ってくるエッジ）と出次数（出ていくエッジ）がゼロになりました。これで、ノード「E」に関するすべての前提条件が満たされました。ここで、「E」をキューの末尾に追加します。これで残りのノードがなくなり、アルゴリズムはここで終了します。

ニックネーム Code トポロジカルソートの場合

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

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 0 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より大きい値です。
• 入次数がゼロのノードが見つからなかったため、空のキューを返します。

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

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

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

ステップ3） 要素の数が頂点の総数と等しい場合、サイクルは存在しない。

ステップ4） 頂点の数と等しくない場合、与えられたグラフデータ構造には少なくとも1つのサイクルが存在する。

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

アルゴリズムの複雑さには2種類あります。それは以下のとおりです。

1. 時間の複雑さ
2. スペースの複雑さ

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

時間計算量： トポロジカルソートの時間計算量はすべて同じです。時間計算量には、最悪、平均、最良という3つのシナリオがあります。トポロジカルソートの時間計算量は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」のトポロジーソートを使用してパッケージの依存関係をチェックします。

よくあるご質問