Darstellung gewichteter Diagramme

Gewichtete Kanten können in Adjazenzlisten gespeichert werden.

Es gibt zwei Arten gewichteter Diagramme: scheitelpunktgewichtete und kantengewichtete Diagramme. In einem scheitelpunktgewichteten Diagramm wird jedem Scheitelpunkt eine Gewichtung zugewiesen. In einem kantengewichteten Diagramm wird jeder Kante ein Gewicht zugewiesen. Von den beiden Typen haben kantengewichtete Diagramme mehr Anwendungsmöglichkeiten. In diesem Kapitel werden kantengewichtete Diagramme betrachtet.

Gewichtete Diagramme können auf die gleiche Weise wie ungewichtete Diagramme dargestellt werden, mit der Ausnahme, dass Sie die Gewichte an den Kanten darstellen müssen. Wie bei ungewichteten Diagrammen können die Scheitelpunkte in gewichteten Diagrammen in einem Array gespeichert werden. In diesem Abschnitt werden drei Darstellungen für die Kanten in gewichteten Diagrammen vorgestellt.

Darstellung gewichteter Kanten: Kantenarray

Gewichtete Kanten können mithilfe eines zweidimensionalen Arrays dargestellt werden. Sie können beispielsweise alle Kanten im Diagramm in Abbildung unten (a) mithilfe des Arrays in Abbildung unten (b) speichern.

Gewichte können jeden Typ haben: Integer, Double, BigDecimal und so weiter. Sie können ein zweidimensionales Array vom Typ Object verwenden, um gewichtete Kanten wie folgt darzustellen:

Objekt[][] Kanten = {
{new Integer(0), new Integer(1), new SomeTypeForWeight(2)},
{new Integer(0), new Integer(3), new SomeTypeForWeight(8)},
...
};

Gewichtete Adjazenzmatrizen

Angenommen, der Graph hat n Eckpunkte. Sie können eine zweidimensionale n * n-Matrix, beispielsweise Gewichte, verwenden, um die Gewichte an Kanten darzustellen. weights[i][j] stellt das Gewicht auf der Kante dar (i, j). Wenn die Eckpunkte i und j nicht verbunden sind, ist weights[i][j] null. Beispielsweise können die Gewichte im Diagramm in Abbildung oben (a) mithilfe einer Adjazenzmatrix wie folgt dargestellt werden:

Adjazenzlisten

Eine andere Möglichkeit, die Kanten darzustellen, besteht darin, Kanten als Objekte zu definieren. Die Klasse AbstractGraph.Edge wurde so definiert, dass sie eine ungewichtete Kante in AbstractGraph.java darstellt. Für gewichtete Kanten definieren wir die Klasse WeightedEdge wie im Code unten gezeigt.

AbstractGraph.Edge ist eine innere Klasse, die in der Klasse AbstractGraph definiert ist. Es stellt eine Kante vom Scheitelpunkt u bis v dar. WeightedEdge erweitert AbstractGraph.Edge um eine neue Eigenschaft weight.

Um ein WeightedEdge-Objekt zu erstellen, verwenden Sie new WeightedEdge(i, j, w), wobei w das Gewicht auf der Kante ist (i , j). Oftmals muss man die Gewichte der Kanten vergleichen. Aus diesem Grund implementiert die Klasse WeightedEdge die Schnittstelle Comparable.

Für ungewichtete Diagramme verwenden wir Adjazenzlisten zur Darstellung von Kanten. Für gewichtete Diagramme verwenden wir immer noch Adjazenzlisten. Die Adjazenzlisten für die Eckpunkte im Diagramm in Abbildung unten a können wie folgt dargestellt werden:

java.util.List[] list = new java.util.List[5];

list[i] speichert alle Kanten neben dem Scheitelpunkt i.

Aus Gründen der Flexibilität verwenden wir eine Array-Liste anstelle eines Arrays fester Größe, um die Liste wie folgt darzustellen:

Liste> list = new java.util.ArrayList();

Das obige ist der detaillierte Inhalt vonDarstellung gewichteter Diagramme. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!