Repräsentieren Graph in Tabelle und gegebene besuchten Knoten, die nächsten

Question

besuchen Knoten Sagen, ich habe einen Graph mit n Knoten 111.222, ..., nnn und ich habe den in der folgenden Tabelle dargestellt Graph zum Beispiel

NodeID | PredecessorID 
222   111 
333   111 
555   222 
555   333 

und so weiter.

eine Liste der M Knoten gegeben, die besucht wurden, wie kann ich alle Knoten finden, die als nächstes besucht werden sollen? Ein Knoten, der als nächstes besucht werden soll, ist ein Knoten, der alle seine Vorgänger besucht hat.

Answer 1

Wenn Ihre Liste M alle besuchten Knoten enthält und nicht nur einen Teil von ihnen können Sie es wie folgt tun:

foreach n in N: 
    visite = True 
    if n is not marked: 
     foreach predecessor (pn) of n: 
      visite = visite and (is pn marked) 

    if visite = True: 
     add n to visitable nodes 

Im schlimmsten Fall wird die Anzahl von predecessors of n ist N (komplette Grafik), so dass die Laufzeit Komplexität davon ist O (N^2)