Aufteilen eines gerichteten azyklischen Graphen (DAG) in Komponenten, dann Suchen des Stamm- und letzten untergeordneten Objekts in diesen Komponenten

Question

Ich möchte ein Diagramm in seine Komponenten aufteilen (wie im folgenden Beispiel DAG). Beachten Sie die farbigen Kennungen jedes Knotens, wie sie dargestellt werden die Komponenten). Nachdem ich die Komponenten im Bild gefunden habe, möchte ich den Stamm und das letzte Kind dieser Komponente finden. Nehmen wir zum Beispiel die Komponente blue, die Wurzel ist E und das letzte Kind ist H. Grün: Wurzel B - letztes Kind H.

Beispiel grafische Darstellung:

Wenn Sie eine Verbindung zwischen E finden - H, B-E, B-H, A-I ohne sie in Komponenten aufzuteilen. Lass es mich wissen, denn das ist mein letztes Ziel.

Über das Kompilieren von Komponenten. Das ist eigentlich mein Endziel. Ich wollte das nur einbeziehen, um vielleicht ein besseres Verständnis dafür zu bekommen, was ich erreichen möchte. Das kann ich nicht, wenn ich diese Verbindungen finde.

Fragen fand ich hilfreich, aber meine Frage nicht beantwortet:

• Algorithm to find lowest common ancestor in directed acyclic graph?

• Finding best common ancestor of two leaf nodes where nodes have zero, one, or two parents

(Diese Antworten ausreichend sein, aber ich weiß nicht, wie zu implementieren es)

Hinweis:

• Bitte senden Sie alle Beispielcode in C++ oder C# (wenn du gehst, Beispiel-Code schreiben)

• Dies ist meine erste Frage. Wenn ich etwas falsch gemacht habe, lass es mich wissen.

// Big edit: Überarbeitete die Frage zu machen, mehr klar, was ich will. Einführung von Komponenten, wie ich denke, dass das hilfreicher sein wird.

Answer 1

zu lang für einen Kommentar, aber ich glaube nicht, dass Sie alle die gemeinsamen Vorfahren zu finden:

Von wikipedia:

In der Graphentheorie und Informatik, den kleinsten gemeinsamen Vorfahren (LCA) von zwei Knoten v und w in einem Baum oder gerichteten azyklischen Graphen (DAG) ist der niedrigste (dh tiefste) Knoten, der sowohl v als auch w als Nachkommen hat, wobei wir jeden Knoten als Nachkommen von sich selbst definieren (also wenn v einen direkte Verbindung von w, w ist der niedrigste gemeinsame Vorfahre).

Wenn Sie die LCA der Eltern betrachten, dann gibt es vier Eltern von Vertex H die C sind, D, F und G dann können Sie die LCA prüfen die Werte für jedes Paar von Eltern sein:

• LCA(C, D) = B
• LCA(C, F) = C
• LCA(C, G) = C
• LCA(D, F) = D
• LCA(D, G) = D
• LCA(F, G) = E

so sind die Ökobilanzen der Eltern von HB, C, D und E.

Die gemeinsamen Vorfahren wird die niedrigsten gemeinsamen Vorfahren (n) und ihre Vorfahren sein - so A, B, C, D und E.

Sie müssen angeben, warum A, C und als gemeinsame Vorfahren ausgeschlossen werden.