Das Konzept des Diagramms
Die Grafik ist die Ausdehnung des Baumes im Algorithmus. Der Baum ist eine Datenstruktur von oben nach unten. Die Knoten haben einen übergeordneten Knoten (mit Ausnahme des Stammknotens), der von oben nach unten angeordnet ist. Die Grafik hat kein Konzept von Vater-Sohn-Knoten, und die Knoten in der Grafik sind alle gleiche Beziehungen, was das Ergebnis noch komplizierter macht.
Ungerichtete Grafik -Graphen -Diagramme
Abbildung G = (V, E), wobei V den Scheitelpunkt darstellt, e die Kantekante darstellt, und eine Kante ist ein Festpunktpaar (U, V), wobei (u, v) ∈V.
In den letzten zwei Tagen stieß ich auf einen Algorithmus über Grafiken. Ich habe lange online gesucht und konnte die Java -Version der Grafiken in der Datenstruktur und deren zugehörigen Operationen nicht finden. Also fand ich eine Java -Version des Datenstrukturbuchs und las es. Das Folgende ist eine Zusammenfassung des ungerichteten Graphenspeichers und der Tiefenprioritätsquelle von Graphen, die basierend auf der Erklärung des Buches erstellt wurden. Dieser Traversal kann jedoch nur das angeschlossene Diagramm durchqueren und das nicht vernetzte Graphen durchqueren, muss sie weiterhin geändert werden. Ich hoffe, es wird für die Bedürftigen hilfreich sein.
Paket com.homework;/*** Definieren Sie die Stack -Klasse*/class stackx {private endgültige int size = 20; private int [] st; private int top; // Initialisieren Sie den Stack public stackx () {st = new int [size]; top = -1;} // Initialisieren Sie den Stack Public void push () int j) top ({++ top] = j; ST [TOP-];} // RECHTEN SIE DAS TOP ELEMET DER STACK PUBLIC INT PEAK () {Return St [Top];} // Bestimmen Sie, ob der Stapel leer ist, public boolean isempty () {return (top ==-1);}}/** * Define Die Knotenklasse in der Grafik *Author-Administratorin. LAB) {Label = Lab; war besucht = false;}}/** * Definieren Sie die Graph -Klasse * @Author Administrator * */Klasse Graph {private endgültige int num = 20; private vertex vertexlist []; // node array privat int adjmat [] []; // Knotenmatrix private Invers; // Die aktuelle Nummer der Nodes privat -graph -fitness the stackx thestack; Graph () {vertexlist = neuer Vertex [num]; adjMat = new int [num] [num]; nverts = 0; für (int i = 0; i <num; i ++) {für (int j = 0; j <num; j ++) adjmat [i] [j] = 0;}} // add node public adds adds adds adds adds addox (Char) adds add. Scheitelpunkt (Labor);} // Fügen Sie eine Kante zwischen zwei Knoten public void hinzu (int start, int end) {adjmat [start] [Ende] = 1; adjmat [Ende] [Start] = 1;} // Ausgabe eines bestimmten Knotens public void displayvertex (in v) {system.out.print (Vertexlist) intelllist [v] .LLABEL. getAdjUnvisitedVertex(int v){for (int j=0; j<nVerts; j++){if(adjMat[v][j]==1 && vertexList[j].wasVisited==false) return j;}return -1;}//Deep priority traversal (DFS) public void dfs () {vertexlist [0] .waSVIDIDED = true; dosidgevertex (0); thestack = new stackx (); thestack.push (0); while (! theStack.isempty ()) {int v = getAdjunvidedvertex (thestack.peak ()); if (v ==-1) // Wenn der Knoten nicht existiert, thestack.pop (); sonst {vertexlist [v]. wurde besucht = true; displayvertex (v); thestack.push (v);}} für (int j = 0; j <nverts; j ++) Vertexlist [j] .WaSVIVED = false;}} öffentliche Klasse GraphConnect {public static void main (String [] args) {{graph thegraph = new Graph (); thegraph.addvertex ('a'); thegraph.addvertex ('b'); thegraph.addvertex ('c'); thegraph.addvertex ('d'); thegraph.addvertex ('e'); theGraph.addEdge(0, 1);//AB theGraph.addEdge(1, 2);//BC theGraph.addEdge(0, 3);//AD theGraph.addEdge(3, 4);//DE theGraph.addEdge(2, 4);//CE System.out.print("The order besucht: "); thegraph.dfs (); System.out.println ();}}} Ergebnisse des Programms laufen:
Die Besuchsbefehl: ABCED
Zusammenfassen
Das obige ist die detaillierte Erklärung des Speicher- und DFS -Betriebscodes der Java -Programmierung ungerichteter Graphenstruktur. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf diese Seite verweisen:
Java-Programmierung implementiert eine grafische Tiefensuche und die Breite, die zuerst die suchende Tiefe-zu-First-Suchcode
Tiefe-First- und Breadh-First-Java-Implementierungscode Beispiel für Java-Implementierungscode
Java -Programmierkonvertierungscode für zwei Baummenüstrukturen
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!