Verschiedene Möglichkeiten DAGs in Java zu implementieren

Question

ich DAG bin der Umsetzung und sich fragen, ob die folgende der einzige Weg ist es in Java zu repräsentieren:

class Node{ 
List<Node> parents; 
List<Node> successors; 
int value; } 

class DAG{ 
Node root; // assuming only one root exists 
} 

ich suche etwas einfacher ohne zwei Listen für Eltern und Kinder.
ist es möglich? Auch ich habe ein Problem mit dieser Darstellung, dass, wenn ich einen bestimmten Knoten x erreicht und wollte den Weg von x zum Wurzelknoten, wie kann ich es finden, ohne durch alle Eltern gesetzt zu gehen?

Answer 1

Ihre gerichteten Graphen-Struktur zu vereinfachen, ist es nicht notwendig für Knoten Links zu ihren Vorfahren zu haben, zurück. Ich würde auch die Node-Klasse in Ihrer DAG-Klasse platzieren. Konzeptionell macht diese Darstellung sowieso mehr Sinn, da in einem gerichteten Graphen, wenn Knoten A mit Knoten B verknüpft ist, kein Pfad von B nach A vorhanden sein muss. Tatsächlich kann kein Pfad in beiden Richtungen existieren, da dies ein Zyklus wäre.

public class DAG { 
    Node root; // assuming only one root exists 

    public static class Node{ 
     List<Node> successors; 
     int value; 
    } 
} 

Um den Pfad vom Stamm zu einem bestimmten Knoten zu finden, müssen Sie einen Algorithmus ausführen, um das Diagramm zu durchsuchen. Das bedeutet, dass Sie möglicherweise die anderen Knoten im Diagramm möglicherweise rekursiv besuchen, bis Sie den angegebenen Knoten gefunden haben. Wenn Sie diese Art von Berechnungen zu wiederholen vermeiden wollen, können Sie auch den Pfad speichern aus dem Wurzel zu einem bestimmten Knoten mit etwas wie folgt aus:

class PathMap { 
    HashMap<DAG.Node, List<DAG.Node> > pathMap; 

    public List<DAG.Node> getPathFromRoot(DAG.Node n) { 
    List<DAG.Node> pathFromRoot = pathMap.get(n); 
    return pathFromRoot; 
    } 
} 

Nun kann es zu einem von der Wurzel mehrere verschiedene Pfade sein gegebener Knoten. In diesem Fall möchten Sie möglicherweise einen shortest-path-first algorithm implementieren, um den optimalen Pfad zu finden und zu speichern. Siehe dzone article für Pseudocode.

Answer 2

Unabhängig davon, ob es sinnvoll ist, die Eltern Liste fällt, hängt von Ihrem typischen Anwendungsfall. Wie Thorn darauf hingewiesen hat, können Sie die Eltern grundsätzlich in eine DAG fallen lassen, wie sie implizit von den Kindern (oder den Eltern) gegeben werden. Wenn Sie jedoch in Ihren Anwendungen häufig einen oder mehrere Vorfahren eines bestimmten Knotens finden müssen, können die Elternlisten dabei helfen, einen schnellen Algorithmus zu implementieren (da Sie nicht immer vom Stamm aus starten und möglicherweise traversieren müssen) der ganze Graph, anstatt rückwärts so weit wie nötig von dem gegebenen Knoten zu gehen).

Ich würde dies als Kommentar zu Thorn Antwort hinzugefügt haben, aber haben nicht genug rep zu kommentieren. Also zögern Sie nicht, es in seine Antwort aufzunehmen.