Python トポロジカル ソート
このチュートリアルでは、Python でのトポロジカル ソート アルゴリズムの実装について説明します。
Python のトポロジカル ソート アルゴリズム
トポロジカル ソート アルゴリズムは、有向非巡回グラフ (DAG) をソートします。 有向非巡回グラフ (DAG) は、あるノードから別のノードへの有向エッジを持ち、循環を持たないグラフです。
トポロジカル ソートは、DAG を入力として受け入れ、各ノードが指すノードの前に表示される配列を返すアルゴリズムです。
DAG 以外のグラフには適用できません。トポロジカル ソートでは、ノード間のエッジの方向に順序が完全に依存し、グラフ内にサイクルがある場合、複数の配置が存在する可能性があるためです。
結果として、有向非巡回グラフのノードのトポロジカルな並べ替えは、エッジ (i,j) が存在する場合、i が j の前に来るような順序でノードを配置するアクションであると言えます。 リスト内。
トポロジカル ソートは基本的に、タスクを実行する順序を提供し、グラフにサイクルがあるかどうかを判断するのに役立ちます。
すべてのグラフは、複数のトポロジー順序をサポートする場合があります。 グラフ内のノードのインディグリーによって決まります。
さらに、ネットワークのトポロジー順序付けは、次数が 0 のノード、つまり入力エッジのないノードから始まります。
トポロジカル ソートで何が起こっているかをよりよく理解するために、例を見てみましょう。
入力 DAG:
最初の反復: []
2 回目の反復: [B]
3 回目の反復: [B, E]
4 回目の反復: [B, E, A]
5 回目の反復: [B, E, A, F]
最終出力: [B, E, A, F, C, D]
上記の例では、グラフから入力エッジのないノードを繰り返し削除し、それを配列に入れています。 グラフにノードが 1つだけ残るまで、このプロセスを繰り返します。
最後に、この最終ノードを配列の最後に追加します。
Python でトポロジカル ソート アルゴリズムを実装する
上記で説明したのと同じロジックを実装して、Python でトポロジカル ソート プログラムを作成できます。 このアルゴリズムをコードに実装する手順を以下に示します。
- 入力エッジがないノードを特定します。
- このノードとそれに対応するエッジをグラフから削除します。
- 隣接ノードの入次数を更新します。
- グラフが空になるまで、手順 1 ～ 3 を繰り返します。
これらの 4つのステップから、トポロジカル ソート用のグラフを作成する必要があることは明らかです。 これには複数の方法がありますが、最も便利な方法は、ノードとエッジをグラフに挿入するためのメソッドを含む graph クラスを作成することです。
次のコード スニペットは、グラフにエッジを追加するコンストラクタとメソッドを含む graph クラスを示しています。
from collections import defaultdict
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def addEdge(self, frm, to):
self.graph[frm].append(to)
if self.directed is False:
self.graph[to].append(frm)
else:
self.graph[to] = self.graph[to]
これで、有向グラフまたは無向グラフを初期化できる graph という名前のクラスと、グラフにエッジを追加するために使用できるメソッド addEdge() ができました。
今必要なのは、トポロジカル ソート アルゴリズムを実装するメカニズムだけです。 ノードにアクセスし、着信エッジがないかどうかを確認し、着信エッジがない場合はそのノードを削除する関数を作成する必要があります。
このタイプの関数を次のコード スニペットに示します。
def visitNode(self, s, visited, sortlist):
visited[s] = True
for i in self.graph[s]:
if not visited[i]:
self.visitNode(i, visited, sortlist)
sortlist.insert(0, s)
上記の関数は、現在のノード s のインデックスを取得します。 ノードがすでに訪問されているかどうかに関する情報を含むブールリストvisitedと、グラフから削除されたノードを保存するために使用するsortlist。
グラフ内のすべてのノードに対してこの visitNode() をインクリメンタルに呼び出し、ソートされたリストの値を最後に出力する別のヘルパー関数を作成する必要があります。 次のコード スニペットは、Python で実装された同様の関数を示しています。
def topologicalSort(self):
visited = {i: False for i in self.graph}
sortlist = []
for v in self.graph:
if not visited[v]:
self.visitNode(v, visited, sortlist)
print(sortlist)
これで、graph クラスの実装が完了しました。 グラフを作成し、topologicalSort() 関数を呼び出してリストをソートする必要があります。
このプロセスは、次のコードで実装されています。
if __name__ == "__main__":
graph = Graph(directed=True)
graph.addEdge(1, 6)
graph.addEdge(1, 3)
graph.addEdge(2, 1)
graph.addEdge(2, 5)
graph.addEdge(3, 4)
graph.addEdge(5, 1)
graph.addEdge(5, 6)
graph.addEdge(5, 6)
graph.addEdge(6, 3)
graph.addEdge(6, 4)
print("Topological Sort Algorithm:")
graph.topologicalSort()
出力：
Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example
このコードで作成したグラフは、上記の図の図に対応しています。 ここで、インデックス 1 から 6 はノード A から F を参照します。
これまで見てきたように、最終的にソートされたリストは [B, E, A, F, C, D] であり、これはコードの出力と同じです。
では、上記のコードを 1つのコード ブロックにまとめたものを見てみましょう。
from collections import defaultdict
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def addEdge(self, frm, to):
self.graph[frm].append(to)
if self.directed is False:
self.graph[to].append(frm)
else:
self.graph[to] = self.graph[to]
def visitNode(self, s, visited, sortlist):
visited[s] = True
for i in self.graph[s]:
if not visited[i]:
self.visitNode(i, visited, sortlist)
sortlist.insert(0, s)
def topologicalSort(self):
visited = {i: False for i in self.graph}
sortlist = []
for v in self.graph:
if not visited[v]:
self.visitNode(v, visited, sortlist)
print(sortlist)
if __name__ == "__main__":
graph = Graph(directed=True)
graph.addEdge(1, 6)
graph.addEdge(1, 3)
graph.addEdge(2, 1)
graph.addEdge(2, 5)
graph.addEdge(3, 4)
graph.addEdge(5, 1)
graph.addEdge(5, 6)
graph.addEdge(5, 6)
graph.addEdge(6, 3)
graph.addEdge(6, 4)
print("Topological Sort Algorithm:")
graph.topologicalSort()
出力：
Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example
これでチュートリアルは終了です。 これで、トポロジカル ソートがどのように機能するかを完全に理解して実装できます。
Maisam is a highly skilled and motivated Data Scientist. He has over 4 years of experience with Python programming language. He loves solving complex problems and sharing his results on the internet.
LinkedIn