Python トポロジカルソート
Python3 実例有向非巡回グラフ（Directed Acyclic Graph、略称DAG）Gに対してトポロジカルソートを行うとは、Gのすべての頂点をひとつの線形列に並べ、グラフ内の任意の頂点の組uとvについて、辺(u,v)∈E(G)ならば、uが線形列内でvより前に現れるようにすることである。通常、このような線形列はトポロジカルオーダー（Topological Order）を満たす列と呼ばれ、略してトポロジカル列と呼ばれる。簡単に言えば、ある集合上の半順序からその集合上の全順序を得る操作をトポロジカルソートと呼ぶ。
グラフ理論において、有向非巡回グラフの頂点からなる列が、以下の条件を満たす場合に限り、そのグラフのトポロジカルソート（英語: Topological sorting）と呼ばれる。
- 各頂点はちょうど一度だけ現れる；
- Aが列の中でBより前に並ぶ場合、グラフ内にBからAへの経路は存在しない。
実例
from collections import defaultdict
class Graph:
def __init__(self,vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self,u,v):
self.graph[u].append(v)
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
def topologicalSort(self):
visited = [False]*self.V
stack =[]
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
print (stack)
g= Graph(6)
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
print ("トポロジカルソート結果：")
g.topologicalSort()
上記のコードを実行すると、出力結果は次のようになります：
拓扑排序结果： [5, 4, 2, 3, 1, 0]その他の拡張