Ich habe eine topologische Sortierung basierend auf dem Wikipedia-Artikel implementiert, den ich für die Abhängigkeitsauflösung verwende, aber es wird eine lineare Liste zurückgegeben. Welche Art von Algorithmus kann ich verwenden, um die unabhängigen Pfade zu finden?
13
Antworten:
Ich gehe davon aus, dass eine Kante bedeutet, dass u ausgeführt werden muss, bevor v . Ist dies nicht der Fall, drehen Sie alle Kanten um. Ich gehe außerdem davon aus, dass Sie weniger an Pfaden interessiert sind (diese sind bereits von der DAG vorgegeben) als an einer guten Ausführungsstrategie aufgrund der Abhängigkeiten.( u , v ) u v
Sie können die topologische Sortierprozedur einfach anpassen: Anstatt anzuhängen, fügen Sie alle Elemente mit derselben "Tiefe" zu einem Satz zusammen. Sie erhalten eine Liste von Sets, von denen jedes Elemente enthält, die Sie parallel ausführen / installieren können. Formal sind die Mengen für den Graphen G = ( V , E ) wie folgt definiert :Sich G = ( V, E)
wo
und
T.count
ist ein einfacher Zähler, der die Anzahl derT
bereits ausgeführten Vorgänger ,T.indeg
die Anzahl der Vorgänger undT.succ
die Menge der Nachfolger enthält.quelle