Wie kann ich einen gewichteten, gerichteten Graphen in Java darstellen?

Question

Ich kann keine externen Bibliotheken verwenden, also versuche ich mir einige Möglichkeiten zu überlegen, die Datenstruktur selbst zu erstellen. Ich dachte, vielleicht etwas in der Art:

public class Node{ 
    Set<Edge> adjacent; 
    int value; 
} 

public class Edge{ 
    Node target; 
    int weight; 
} 

Aber ich vermute, es gibt wahrscheinlich einen besseren Weg, es zu tun.

Mein eventueller Gebrauch für dieses Diagramm ist, den Bellman Ford-Algorithmus darauf auszuführen, aber ich brauche offensichtlich zuerst ein funktionierendes Diagramm!

Answer 1

Die Antwort hängt sehr von den Algorithmen ab, die Sie auf Ihre Graphen anwenden möchten.

Es gibt zwei gebräuchliche Arten, eine Grafik darzustellen - eine adjacency list und eine adjacency matrix. In Ihrem Fall ist die Adjazenzmatrix eine quadratische Matrix mit Ganzzahlen, die Gewichte darstellen. Ihre Darstellung verwendet eine Adjazenzliste.

Es gibt Algorithmen, die besser auf Adjazenzmatrizen (z. B. Floyd-Warshall-Algorithmus) arbeiten. Andere Algorithmen arbeiten besser bei Adjazenzlisten (z. B. Dijkstra-Algorithmus). Wenn Ihr Diagramm spärlich ist, kann die Verwendung der Adjazenzmatrix unerschwinglich sein.

Answer 2

Wie üblich können Sie Graphen als Adjazenzlisten oder Adjazenzmatrizen darstellen. Die Wahl hängt wirklich von den Details Ihres Problems ab.

Mit einer Adjazenzmatrix können Sie einfach eine Matrix von ganzen Zahlen haben, die das Gewicht darstellen.

Wenn Sie sich für eine Adjazenzliste entscheiden, können Sie einfach eine Liste der Ganzzahlen speichern (vorausgesetzt, die Knoten Ihres Diagramms sind durch einen ganzzahligen Wert gekennzeichnet), ähnlich wie bei Ihnen.

Answer 3

einen Knoten, wie in einem ungewichteten Graph verwenden kann, um eine Liste von Knoten halten, die er angeschlossen ist, und fügt zusätzlich die mit den Anschlüssen verbunden sind Gewichte als:

public class Node{ 
    int value; 
    HashMap<Node,Integer> adjacency; 
}