Traversal cyclischer Digraph

Question

Ich habe einen zyklischen gerichteten Graphen. Beginnend an den Blättern, mag ich fortzupflanzen Daten an jeden Knoten an alle Knoten stromabwärts angebracht, der von diesem Knoten erreichbar sind. Insbesondere muß ich halte Daten um irgendwelche Zyklen drängen, die erreicht werden, bis die Zyklen stabilisieren.

Ich bin ganz sicher, dass dies ein Lager Graph Traversal Problem. Allerdings bin ich ein gutes Stück von Schwierigkeiten, die versuchen, einen geeigneten Algorithmus zu finden --- Ich glaube, ich bin ein paar entscheidende Suchbegriffen fehlt.

Bevor ich versuche, meinen eigenen halbherzig O (n ^ 3) Algorithmus, kann jeden Punkt mich in einer geeigneten Lösung zu schreiben? Und was dieses spezielle Problem genannt?

Answer 1

Da der Graph cyclisch ist (d.h. Zyklen enthalten kann), würde ich es zuerst brechen in stark verbundenen Bauteile. Ein stark Komponente eines gerichteten Graphen verbunden ein Teilgraph ist, wobei jeder Knoten von jedem anderen Knoten erreichbar ist, in das gleiche Subgraphen. Dies würde eine Reihe von Untergraphen ergeben. Beachten Sie, dass eine stark verbundene Komponente von mehr als einem Knoten effektiv ein Zyklus ist.

Nun, in jeder Komponente, alle Informationen in einem Knoten werden schließlich in jedem anderen Knoten des Graphen am Ende (da sind sie alle erreichbar). Damit für jeden Untergraphen können wir alle Daten von allen Knoten in sie nehmen einfach und jeder Knoten die gleiche Menge von Daten machen. Keine Notwendigkeit zu halten, durch die Zyklen gehen. Auch am Ende dieses Schritts werden alle Knoten in der gleichen Komponente enthält genau die gleichen Daten.

Der nächste Schritt jeder stark verbundenen Komponente in einem einzigen Knoten kollabieren würde. Da die Knoten innerhalb derselben Komponente alle die gleichen Daten haben, und sind daher im Grunde das gleiche, ist dieser Vorgang nicht wirklich die Grafik ändern. Der neu geschaffene „Superknoten“ erbt alle Kanten ausgehen oder kommen in die Komponente Knoten von Knoten außerhalb der Komponente.

Da wir all stark verbundene Komponenten zusammengebrochen sind, gibt es keine Zyklen in dem resultierenden Graph (warum? Weil hatte ein Zyklus gibt es durch den resultierenden Knoten gebildet, würden sie alle in der gleichen Komponente an erster Stelle platziert worden sind ). Der sich ergebende Graph ist nun ein gerichteten azyklischen Graphen . Es gibt keine Zyklen und eine einfachen Tiefe Traversal von allen Knoten mit indegree = 0 (dh Knoten, die keine eingehenden Kanten), Daten von jedem Knoten zu seinem benachbarten Knoten ausbreitet (dh seiner „Kinder“), sollte den Job erledigen .