Topologisch sortierter Graph in Buckets für disjunkte Subgraphen

Question

Ich suche einen Algorithmus, der einen Graph aufnehmen und topologisch so sortieren kann, dass er eine Menge von Listen erzeugt, die jeweils die topologisch sortierten Vertices eines disjunkten Subgraphen enthalten.

Der schwierige Teil besteht darin, die Listen zusammenzuführen, wenn ein Knoten von einem Knoten in zwei verschiedenen Listen abhängt.

Hier ist mein unvollständiger Code/Pseudo-Code, wo Graph, der ein dict {node: [node, node, ...]}

topologisch sortieren Graph in disjunkte Listen

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

Erste teilt es in disjunkte Teilgraphen ist eine Flußfüllen Algorithmus, und dann topologisch sortieren Jeder.