Wir wissen, dass wir sie mit einem eindimensionalen Array darstellen können, um Knoten darzustellen. Für die Beziehung zwischen Knoten können wir sie jedoch nicht einfach mit einem eindimensionalen Array darstellen. Wir können sie mit einem zweidimensionalen Array darstellen, dh einer matrixbildenden Darstellungsmethode.
Wir gehen davon aus, dass a dieses zweidimensionale Array ist, dann spiegelt ein Element AIJ in einer Beziehung nicht nur die Beziehung zwischen Knoten VI und Knoten VJ wider, sondern auch den Wert von AIJ kann die Größe des Gewichts darstellen.
Benachbarte Matrixmodellklasse
Der Klassenname der Adjazenzmatrix -Modellklasse ist amwgraph.java. Es kann einen Diagramm erstellen, der durch eine Adjazenzmatrix durch diese Klasse dargestellt wird, und Insertionsknoten bereitstellen, Kanten einfügen und den ersten Adjazenzknoten und den nächsten Adjazenzknoten eines bestimmten Knotens erhalten.
Import Java.util.ArrayList;
import Java.util.linkedList;
öffentliche Klasse Amwgraph {
private arrayList vertexlist;
// Die Link -Tabelle der Speicherpunkte
private int [] [] Kanten;
// Adressmatrix, zum Speichern von Kanten verwendet
private int numofedges;
// Anzahl der Kanten
public amwgraph (int n) {
// Initialisieren Sie das Matrix, ein eindimensionales Array und die Anzahl der Kanten
Kanten = new int [n] [n];
vertexlist = new ArrayList (n);
numofedges = 0;
}
// Holen Sie sich die Anzahl der Knoten
public int getnumofvertex () {
return vertexlist.size ();
}
// Erhalten Sie die Anzahl der Kanten
public int getnumofedges () {
Rückgabezahlen;
}
// Geben Sie die Daten des Knotens I zurück
öffentliches Objekt GetValuebyIndex (int i) {
Rückgabe vertexlist.get (i);
}
// das Gewicht von V1 und V2 zurückgeben
public int GetWeight (int v1, int v2) {
Rückgabekanten [v1] [v2];
}
// Knoten einfügen
public void Insertvertex (Objektscheitelpunkt) {
vertexlist.add (vertexlist.size (), vertex);
}
// Knoten einfügen
public void Insertge (int v1, int v2, int Gewicht) {
Kanten [v1] [v2] = Gewicht;
numofedges ++;
}
// Knoten löschen
public void deleteedge (int v1, int v2) {
Kanten [v1] [v2] = 0;
numofedges--;
}
// Holen Sie sich den Index des ersten benachbarten Knotens
public int getfirstneigeigbor (int index) {
für (int j = 0; j <vertexlist.size (); j ++) {
if (Kanten [index] [j]> 0) {
Rückkehr J;
}
}
Return -1;
}
// Erhalten Sie den nächsten Adjazenzknoten basierend auf dem Index des vorherigen Adjazenzknotens
public int getNextNeighbor (int v1, int v2) {
für (int j = v2+1; j <vertexlist.size (); j ++) {
if (Kanten [v1] [j]> 0) {
Rückkehr J;
}
}
Return -1;
}
}Schauen wir uns den Code an, der die Adjazenzmatrix implementiert, um dichte Diagramme darzustellen:
Paket com.datastructure.graph;
///// dichte Graph - Verwenden Sie die Adjazenzmatrix, um darzustellen
// öffentliche Klasse Denegraph {
//
// privat int n; // Anzahl der Knoten
// privat int m; // Kantennummer
// privat boolean gerichtet; // Ist es eine gerichtete Grafik
// privat boolean [] [] g; // spezifische Daten des Bildes
//
// // Konstruktor
// public denegraph (int n, boolean inszeniert) {{
// nase n> = 0;
// this.n = n;
// this.m = 0; // Initialisierung hat keine Kanten
// this.directed = Cirected;
// // g wird in eine boolesche Matrix von n*n initialisiert. Jeder g [i] [j] ist falsch und zeigt an, dass es keine und Kanten gibt.
// // false ist der Standardwert der Booleschen Typvariable
// g = neuer Boolescher [n] [n];
//}
//
// public int v () {
// return n;
//} // Die Anzahl der Knoten zurückgeben
//
// public int e () {
// return m;
//} // Die Anzahl der Kanten zurückgeben
//
// // dem Diagramm eine Kante hinzufügen
// public void addgege (int v, int w) {
//
// Assert v> = 0 && v <n;
// Assert w> = 0 && w <n;
//
// if (hasEdge (v, w))
// zurückkehren;
//
// // verbinden v und w
// g [v] [w] = true;
// if (! gerichtet)
// g [w] [v] = true;
//
// // Anzahl der Kanten ++
// m ++;
//}
//
// // Überprüfen Sie, ob in der Grafik Kanten von V zu W vorhanden sind
// boolean hasEdge (int v, int w) {
// Assert v> = 0 && v <n;
// Assert w> = 0 && w <n;
// return g [v] [w];
//}
//
// // Alle Nachbarn eines Scheitelpunkts in der Grafik zurückgeben
// // Da Java einen Referenzmechanismus verwendet, bringt die Rückgabe eines Vektors keinen zusätzlichen Aufwand.
// public iterable <Integer> adj (int v) {
// Assert v> = 0 && v <n;
// vector <Integer> adjv = new Vector <GanzEger> ();
// für (int i = 0; i <n; i ++)
// if (g [v] [i])
// adjv.add (i);
// Return Adjv;
//}
//}
Import Java.util.ArrayList;
importieren java.util.list;
// Verwenden Sie die Adjazenzmatrix, um dichte Diagramme darzustellen
öffentliche Klasse Denegraph {
Privat int n;
// Anzahl der Knoten in der Abbildung
Privat int M;
// Anzahl der Kanten im Bild
privat boolean [] [] g;
// benachbarte Matrix g
privat boolean geleitet;
// Ist es eine gerichtete Grafik
public desegraph (int n, boolean inszeniert) {
this.n = n;
// die Anzahl der Knoten in der Initialisierungsgrafik
this.m = 0;
// Die Anzahl der Kanten in der Abbildung wird auf 0 initialisiert
this.directed = Criected;
g = neuer Boolescher [n] [n];
// Die Adjazenzmatrix G wird in eine zweidimensionale Matrix von N*n initialisiert
// Der Index repräsentiert den Knoten im Diagramm, und der in G gespeicherte Wert ist, ob der Knoten Kanten hat
}
// Geben Sie die Anzahl der Kanten in der Grafik zurück
public int e () {
Rückkehr M;
}
// Geben Sie die Anzahl der Knoten in der Grafik zurück
public int v () {
return n;
}
// Kanten zwischen den beiden in der Abbildung angegebenen Knoten hinzufügen
public void addgege (int v, int w) {
if (! HasEdge (v, w)) {
// verbinden [v] [W]
g [v] [w] = true;
// UNDERRECTED GRAP
if (! gerichtet)
g [w] [v] = true;
// die Anzahl der Seiten im Bild +1
M ++;
}
}
// Bestimmen Sie, ob zwischen den beiden Knoten Kanten vorhanden sind
privat boolean hasedge (int v, int w) {
return g [v] [w];
}
// Gibt die Adjazenzknoten aller Knoten v zurück
public iterable <Integer> AdjAcentNode (int v) {
// benachbart wird verwendet, um den benachbarten Knoten von V zu speichern
Liste <Ganzzahl> adjacentl = new ArrayList <> ();
// Finden Sie alle Knoten neben V und fügen Sie sie zu benachbarten Fügen Sie hinzu
für (int i = 0; i <n; i ++) {
if (g [v] [i])
benachbart (i);
}
Rückkehr benachbarter;
}
}
Zusammenfassen
Das obige ist der gesamte Inhalt dieses Artikels über Java -Programmierung, um das Codebeispiel für eine dichte Graphendarstellung der Adjazenzmatrix zu implementieren, und ich hoffe, dass es für alle hilfreich sein wird. Interessierte Freunde können weiterhin auf diese Seite verweisen:
Analyse grundlegender Konzepte und Codebeispiele für die Java -Datenstrukturbaum
Java Common Data Structure Interview Fragen (mit Antworten)
Multimode -String -Matching -Algorithmus -Prinzip und Java -Implementierungscode
Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!