Verschiedene Wege zur Implementierung des DAGs in java

Ich die Umsetzung DAG und Fragen, ob das folgende ist der einzige Weg, Sie zu vertreten in Java: 

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

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

Ich bin auf der Suche nach 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 erreicht einen bestimmten Knoten x und wollte den Pfad von x zur Wurzel-Knoten, wie ich es finden kann, ohne durch alle Eltern einstellen?

InformationsquelleAutor seteropere | 2013-03-17
  1. 8

    Zur Vereinfachung Ihrer gerichteter graph Struktur ist es nicht erforderlich, für Knoten mit verbindungen zurück zu Ihren Vorfahren. Ich würde auch die Knoten-Klasse in Ihrem DAG-Klasse. Konzeptionell ist diese Darstellung macht mehr Sinn, da eh in einem gerichteten Graphen, wenn die Knoten Eines links zu Knoten B, es muss nicht ein Pfad von B nach A. In der Tat kann es keinen Pfad in beide Richtungen, denn das wäre ein Zyklus.

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

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

    Finden Sie den Pfad von der Wurzel zu einem bestimmten Knoten, die Sie würde ausführen müssen, um einen Algorithmus zu suchen, durch die Grafik. Das bedeutet, auf den anderen Knoten im graph, wahrscheinlich rekursiv, bis Sie die gegebenen Knoten.
    Wenn Sie vermeiden möchten, wiederholen Sie diese Arten von Berechnungen, können Sie auch speichern Sie den Pfad von der
    Wurzel zu einem bestimmten Knoten mit so etwas wie dies:

    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 verschiedene Wege von der Wurzel zu einem bestimmten Knoten. In diesem Fall können Sie umsetzen wollen, ein shortest-path-first-Algorithmus zu finden und zu speichern, die den optimalen Weg. Sehen Sie diese dzone Artikel für pseudocode.

    • Ob oder nicht es sinnvoll ist, fallen die Eltern-Liste hängt von Ihrer typischen Anwendungsfall. Als Dorn wies darauf hin, im Prinzip können Sie drop die Eltern in einer DAG sind, wie Sie sind implizit gegeben durch die Kinder (oder die Eltern). Allerdings, wenn Sie in Ihre Anwendungen, die Sie Häufig benötigen, zu finden einige Vorfahren(s) von einem bestimmten Knoten, die Eltern-Listen, die helfen könnten, zu implementieren, die einen schnellen Algorithmus zu tun (als würde man nicht immer brauchen, um zu starten aus der Wurzel und potenziell Durchlaufen das gesamte Diagramm, statt rückwärts gehen, soweit erforderlich, aus den gegebenen Knoten).
    InformationsquelleAutor Thorn
Schreibe einen Kommentar