Lagerstruktur
Um eine Grafik zu speichern, wissen wir, dass das Diagramm sowohl Knoten als auch Kanten enthält. Für ein angetriebenes Diagramm hat jede Kante auch einen Gewichtswert. Es gibt zwei Haupttypen häufig verwendeter Graphenspeicherstrukturen:
Benachbarte Matrix benachbarte Tabelle
Angrenzende Matrix
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.
Hier ist ein Beispiel für eine Adjazenzmatrixdarstellung eines ungerichteten Graphen:
Aus der obigen Abbildung können wir sehen, dass die Adjazenzmatrix des ungerichteten Diagramms eine symmetrische Matrix ist und eine symmetrische Matrix sein muss. Und der Wert auf der Diagonale von der oberen linken Ecke zur unteren rechten Ecke ist Null (die Diagonale zeigt denselben Knoten an)
Was ist die Adjazenzmatrix eines gerichteten Diagramms?
Für gewichtete Graphen kann der Wert von AIJ verwendet werden, um die Größe des Gewichts darzustellen. Die obigen zwei Grafiken sind Diagramme ohne Gewichte, daher sind ihre Werte beide 1.
Angrenzende Tabelle
Wir wissen, dass die Adjazenzmatrix -Speichermethode des Diagramms eine N*n -Matrix verwendet. Wenn diese Matrix eine dichte Matrix ist (zum Beispiel, wenn das Diagramm ein vollständiges Diagramm ist), wird natürlich die Adjazenzmatrix -Speichermethode ausgewählt.
Wenn diese Matrix jedoch eine spärliche Matrix ist, ist die angrenzende Tabellenlagerstruktur eine leistungssparendere Speicherstruktur.
Für das ungerichtete Diagramm oben können wir eine Adjazenztabelle verwenden, um sie wie folgt darzustellen:
Der mit jedem Knoten verbundene Knoten ist sein benachbarter Knoten.
Vergleich zwischen Adjazenzmatrix und Adjazenztabelle
Wenn die Anzahl der Knoten im Diagramm klein ist und es viele Seiten gibt, ist die Effizienz der Verwendung einer Adjazenzmatrix höher.
Wenn die Anzahl der Knoten sehr groß ist und die Anzahl der Kanten viel kleiner ist als die Anzahl der Kanten des vollständigen Graphen desselben Knotens, ist es effizienter, eine Speicherstruktur der Adjazency -Tabelle zu übernehmen.
Java -Implementierung der Adjazenzmatrix
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;/** * @Description benachbarte Matrix -Modellklasse * @author beanlam * @time 2015.17 */public class Amwgraph {private Arraylist Vertexlist; // Speicherpunkte private Int [] [] // // // adjacent matrix, verwendet, um private int zu lagern. Amwgraph (int n) {// Matrix, eindimensionales Array und Anzahl der Kanten initialisieren = new int [n] [n]; vertexlist = new ArrayList (n); numofedges = 0; } // Die Anzahl der Knoten public int getNumofvertex () {return vertexlist.size (); } // Die Anzahl der Kanten public int getNumofedges () {return numofedges; } // Die Daten des Knotens I public Object GetValuebyIndex (int i) {return vertexlist.get (i); } // das Gewicht von v1, v2 public int get wightweight zurückgeben (int v1, int v2) {return orts [v1] [v2]; } // den Knoten public void insertvertex einfügen (Object vertex) {vertexlist.add (vertexlist.size (), vertex); } // Knoten public void InsertEdge (int v1, int v2, int Gewicht) {Kanten [v1] [v2] = Gewicht; numofedges ++; } // Knoten public void DeleteEdge (int v1, int v2) {Kanten [v1] [v2] = 0; numofedges--; } // den Index des ersten benachbarten Knotens public int getfirstneighbor (int index) {for (int j = 0; j <vertexlist.size (); j ++) {if (regel [index] [j]> 0) {return j; }} return -1; } // den nächsten Adjazenzknoten gemäß 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) {return j; }} return -1; }}Testen der Adjazenzmatrix -Modellklasse
Richten Sie als nächstes die Testmodellklasse basierend auf der folgenden angegebenen Grafik ein
Das Testprogramm testamwgraph.java lautet wie folgt:
/** * @description Test class of AMWGraph class* @author beanlam * @time 2015.4.17 */public class TestAMWGraph { public static void main(String args[]) { int n=4,e=4;//Represents the number of nodes and the number of edges respectively String labels[]={"V1","V1","V3","V4"};//Node Identifikation AMWGRAPH GRAPE = new amwgraph (n); für (String -Etikett: Labels) {Graph.insertvertex (Label); // Node einfügen} // Vier Kanten Graph einfügen. Graph.insertEdge (0, 2, 5); Graph.insertEdge (2, 3, 8); Graph.insertEdge (3, 0, 7); System.out.println ("Die Anzahl der Knoten ist:"+Graph.getNumofvertex ()); System.out.println ("Die Anzahl der Kanten ist:"+Graph.getNumofedges ()); Graph.DeletEedge (0, 1); // Löschen <v1, v2> Edge System.out.println ("Nach dem Löschen <v1, v2> Edge ..."); System.out.println ("Die Anzahl der Knoten ist:"+Graph.getNumofvertex ()); System.out.println ("Die Anzahl der Kanten ist:"+Graph.getNumofedges ()); }}Die Ausgangsergebnisse der Konsole sind in der folgenden Abbildung dargestellt:
Zusammenfassen
Das obige ist der gesamte Inhalt dieses Artikels über die Beschreibung der Java -Sprache der Beispiele für die Speicherstruktur und die Adjazenzmatrix -Code. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen.