トポロジカルなグラフをバケットに分解して分割したサブグラフを作成する

Question

グラフを取ってトポロジカルに並べ替えるアルゴリズムを探しています。それぞれのリストには、トポロジカルなソートされた頂点が含まれています。

ノードが2つの異なるリスト内のノードに依存する場合、難しい部分はリストをマージしています。ここで

はグラフが{node: [node, node, ...]}

位相的にばらばらリストにソートグラフ

sorted_subgraphs = [] 

while graph: 
    cyclic = True 
    for node, edges in list(graph.items()): 
     for edge in edges: 
      if edge in graph: 
       break 
     else: 
      del graph[node] 
      cyclic = False 

      sub_sorted = [] 
      for edge in edges: 
       bucket.extend(...) # Get the list with edge in it, and remove it from sorted_subgraphs 
      bucket.append(node) 

      sorted_subgraphs.append(bucket) 

    if cyclic: 
     raise Exception('Cyclic graph') 

Answer 1

まず塗りつぶしアルゴリズムを使用してばらばら部分グラフに分割して、トポロジカルにソート辞書である私の不完全なコード/擬似コードでありますそれぞれ。