Diagramme darstellen

Die Darstellung eines Diagramms besteht darin, seine Eckpunkte und Kanten in einem Programm zu speichern. Die Datenstruktur zum Speichern eines Diagramms besteht aus Arrays oder Listen. Um ein Programm zu schreiben, das Diagramme verarbeitet und manipuliert, müssen Sie Daten für die Diagramme im Computer speichern oder darstellen.

Scheitelpunkte darstellen

Die Eckpunkte können in einem Array oder einer Liste gespeichert werden. Sie können beispielsweise alle Städtenamen im Diagramm in der Abbildung unten mit dem folgenden Array speichern:

String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", " Miami“, „Dallas“, „Houston“};

Die Eckpunkte können Objekte jeglicher Art sein. Beispielsweise können Sie Städte als Objekte betrachten, die Informationen wie Name, Bevölkerung und Bürgermeister enthalten. Daher können Sie Eckpunkte wie folgt definieren:

Stadt city0 = neue Stadt("Seattle", 608660, "Mike McGinn");
...
Stadt city11 = new City("Houston", 2099451, "Annise Parker");
City[] vertices = {city0, city1, ... , city11};

öffentliche Klasse Stadt {
privater String cityName;
private int Population;
privater String-Bürgermeister;

public City(String cityName, int population, String mayor) {
this.cityName = cityName;
this.population = population;
this.mayor = mayor;
 }

public String getCityName() {
return cityName;
 }

public int getPopulation() {
return population;
 }

public String getMayor() {
return mayor;
 }

public void setMayor(String mayor) {
this.mayor = mayor;
 }

public void setPopulation(int population) {
this.population = population;
 }
}

Die Eckpunkte können bequem mit den natürlichen Zahlen 0, 1, 2, ..., n - 1 für einen Graphen für n Eckpunkte beschriftet werden. Somit steht vertices[0] für „Seattle“, vertices[1] für „San Francisco“ und so weiter siehe Abbildung unten.

Sie können einen Scheitelpunkt über seinen Namen oder seinen Index referenzieren, je nachdem, was bequemer ist. Offensichtlich ist es in einem Programm einfach, über seinen Index auf einen Vertex zuzugreifen.

Kanten darstellen: Kantenarray

Die Kanten können mithilfe eines zweidimensionalen Arrays dargestellt werden. Sie können beispielsweise alle Kanten im Diagramm in Abbildung 28.1 mit dem folgenden Array speichern:

int[][] Kanten = {
{0, 1}, {0, 3}, {0, 5},
{1, 0}, {1, 2}, {1, 3},
{2, 1}, {2, 3}, {2, 4}, {2, 10},
{3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
{4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
{5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
{6, 5}, {6, 7},
{7, 4}, {7, 5}, {7, 6}, {7, 8},
{8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
{9, 8}, {9, 11},
{10, 2}, {10, 4}, {10, 8}, {10, 11},
{11, 8}, {11, 9}, {11, 10}
};

Diese Darstellung wird als Kantenarray bezeichnet. Die Eckpunkte und Kanten in Abbildung unten (a) können wie folgt dargestellt werden:

String[] Namen = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
int[][] Kanten = {{0, 2}, {1, 2}, {2, 4}, {3, 4}};

Kanten darstellen: Kantenobjekte

Eine andere Möglichkeit, die Kanten darzustellen, besteht darin, Kanten als Objekte zu definieren und die Kanten in einer java.util.ArrayList zu speichern. Die Edge-Klasse kann wie folgt definiert werden:

öffentliche Klasse Edge {
int u;
int v;
public Edge(int u, int v) {
this.u = u;
this.v = v;
}
öffentlicher boolescher Wert gleicht(Objekt o) {
return u == ((Edge)o).u && v == ((Edge)o).v;
}
}

Zum Beispiel können Sie alle Kanten im Diagramm in der Abbildung unten mithilfe der folgenden Liste speichern:

java.util.ArrayList list = new java.util.ArrayList<>();
list.add(new Edge(0, 1));
list.add(new Edge(0, 3));
list.add(new Edge(0, 5));
...

Das Speichern von Kanten-Objekten in einer ArrayList ist nützlich, wenn Sie die Kanten nicht im Voraus kennen.

Während die Darstellung von Kanten mithilfe eines Kantenarrays oder von Kanten-Objekten im vorherigen Abschnitt (Kantendarstellung: Kantenarray) und weiter oben in diesem Abschnitt für die Eingabe möglicherweise intuitiv ist, ist sie für die Eingabe nicht effizient interne Verarbeitung. In den nächsten beiden Abschnitten wird die Darstellung von Diagrammen mithilfe von Adjazenzmatrizen und Adjazenzlisten vorgestellt. Diese beiden Datenstrukturen sind effizient für die Verarbeitung von Diagrammen.

Darstellung von Kanten: Adjazenzmatrizen

Angenommen, der Graph hat n Eckpunkte. Sie können eine zweidimensionale n * n-Matrix, beispielsweise adjacencyMatrix, verwenden, um die Kanten darzustellen. Jedes Element im Array ist 0 oder 1. adjacencyMatrix[i][j] ist 1, wenn es eine Kante vom Scheitelpunkt i zum Scheitelpunkt j gibt; andernfalls ist adjacencyMatrix[i][j] 0. Wenn der Graph ungerichtet ist, ist die Matrix symmetrisch, da adjacencyMatrix[i][j] dasselbe ist wie adjacencyMatrix[j][i]. Beispielsweise können die Kanten im Diagramm in der Abbildung unten mithilfe einer Adjazenzmatrix wie folgt dargestellt werden:

int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // Seattle
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // San Francisco
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // Los Angeles
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // Denver
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // Kansas City
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // Chicago
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // Boston
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // New York
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // Atlanta
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // Miami
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // Dallas
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // Houston
};

Da die Matrix für einen ungerichteten Graphen symmetrisch ist, können Sie zum Sparen von Speicherplatz ein unregelmäßiges Array verwenden.

Die Adjazenzmatrix für den gerichteten Graphen in Abbildung unten (a) kann wie folgt dargestellt werden:

int[][] a = {{0, 0, 1, 0, 0}, // Peter
{0, 0, 1, 0, 0}, // Jane
{0, 0, 0, 0, 1}, // Markieren
{0, 0, 0, 0, 1}, // Cindy
{0, 0, 0, 0, 0} // Wendy
};

Kanten darstellen: Adjazenzlisten

Sie können Kanten mithilfe von Adjazenzscheitelpunktlisten oder Adjazenzkantenlisten darstellen. Eine Adjazenzscheitelpunktliste für einen Scheitelpunkt i enthält die an i angrenzenden Scheitelpunkte und eine Adjazenzkantenliste für einen Scheitelpunkt i enthält die an i angrenzenden Kanten. Sie können ein Array von Listen definieren. Die
Das Array hat n Einträge und jeder Eintrag ist eine Liste. Die Adjazenzscheitelpunktliste für Scheitelpunkt i enthält alle Scheitelpunkte j, so dass es eine Kante vom Scheitelpunkt i zum Scheitelpunkt j gibt. Um beispielsweise die Kanten im Diagramm in der Abbildung unten darzustellen, können Sie wie folgt ein Array von Listen erstellen:

java.util.List[] neighbors = new java.util.List[12];

neighbors[0] enthält alle Scheitelpunkte neben dem Scheitelpunkt 0 (d. h. Seattle), neighbors[1] enthält alle Scheitelpunkte neben dem Scheitelpunkt 1 (d. h. San Francisco) und so weiter, wie in der Abbildung unten dargestellt.

Um die Adjazenzkantenlisten für das Diagramm in der Abbildung unten darzustellen, können Sie wie folgt ein Array von Listen erstellen:

java.util.List[] neighbors = new java.util.List[12];

neighbors[0] enthält alle Kanten neben dem Scheitelpunkt 0 (d. h. Seattle), neighbors[1] enthält alle Kanten neben dem Scheitelpunkt 1 (d. h. San Francisco) und so weiter, wie in der Abbildung unten gezeigt.

Sie können ein Diagramm mithilfe einer Adjazenzmatrix oder Adjazenzlisten darstellen. Welches ist besser? Wenn der Graph dicht ist (d. h. es gibt viele Kanten), wird die Verwendung einer Adjazenzmatrix bevorzugt. Wenn der Graph sehr dünn besetzt ist (d. h. sehr wenige Kanten), ist die Verwendung von Adjazenzlisten besser, da die Verwendung einer Adjazenzmatrix viel Platz verschwenden würde.

Sowohl Adjazenzmatrizen als auch Adjazenzlisten können in einem Programm verwendet werden, um Algorithmen effizienter zu machen. Beispielsweise benötigt es eine konstante O(1)-Zeit, um mithilfe einer Adjazenzmatrix zu prüfen, ob zwei Eckpunkte verbunden sind, und es benötigt eine lineare Zeit O(m), um alle Kanten in einem Diagramm mithilfe von Adjazenzlisten auszudrucken, wobei m die Anzahl der Kanten ist .

Adjazenzscheitelpunktliste ist für die Darstellung ungewichteter Diagramme einfacher. Adjazenzkantenlisten sind jedoch für eine Vielzahl von Diagrammanwendungen flexibler. Mithilfe von Adjazenzkantenlisten können Sie ganz einfach zusätzliche Einschränkungen für Kanten hinzufügen. Aus diesem Grund werden in diesem Buch Adjazenzkantenlisten zur Darstellung von Diagrammen verwendet.

Sie können Arrays, Array-Listen oder verknüpfte Listen verwenden, um Adjazenzlisten zu speichern. Wir verwenden Listen anstelle von Arrays, da die Listen leicht erweiterbar sind, sodass Sie neue Scheitelpunkte hinzufügen können. Darüber hinaus werden wir Array-Listen anstelle von verknüpften Listen verwenden, da unsere Algorithmen nur die Suche nach benachbarten Scheitelpunkten in der Liste erfordern. Die Verwendung von Array-Listen ist für unsere Algorithmen effizienter. Mithilfe von Array-Listen kann die Adjazenzkantenliste in der Abbildung unten wie folgt erstellt werden:

List> Nachbarn = neue ArrayList<>();
Nachbarn.add(new ArrayList());
Nachbarn.get(0).add(new Edge(0, 1));
Nachbarn.get(0).add(new Edge(0, 3));
Nachbarn.get(0).add(new Edge(0, 5));
Nachbarn.add(new ArrayList());
Nachbarn.get(1).add(new Edge(1, 0));
Nachbarn.get(1).add(new Edge(1, 2));
Nachbarn.get(1).add(new Edge(1, 3));
...
...
Nachbarn.get(11).add(new Edge(11, 8));
Nachbarn.get(11).add(new Edge(11, 9));
Nachbarn.get(11).add(new Edge(11, 10));

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