Dieser Artikel beschreibt die Implementierungsmethode des Java-basierten Breitendurchlaufalgorithmus für Diagramme in Form von Beispielen. Die spezifischen Methoden sind wie folgt:
Verwenden Sie die Adjazenzmatrix, um die Diagrammmethode zu speichern:
1. Bestimmen Sie die Anzahl der Eckpunkte und Kanten des Diagramms
2. Die eingegebenen Scheitelpunktinformationen werden im eindimensionalen Array-Scheitelpunkt gespeichert
3. Initialisieren Sie die Adjazenzmatrix.
4. Geben Sie nacheinander jede Kante ein und speichern Sie sie im Adjazenzmatrixbogen.
Geben Sie die Seriennummern i und j der beiden an der Kante befestigten Eckpunkte ein.
Setzen Sie den Elementwert der i-ten Zeile und j-ten Spalte der Adjazenzmatrix auf 1;
Setzen Sie den Elementwert der j-ten Zeile und i-ten Spalte der Adjazenzmatrix auf 1;
Breitenorientierte Durchquerungsimplementierung:
1. Initialisieren Sie die Warteschlange Q
2. Besuchsscheitelpunkt v; besuchte Scheitelpunkt v wird zur Warteschlange Q hinzugefügt;
3.while (Warteschlange Q ist nicht leer)
v=Das Kopfelement der Warteschlange Q wird aus der Warteschlange entfernt;
w = erster benachbarter Punkt des Scheitelpunkts v
while(w existiert)
Wenn w nicht besucht wurde, wird der besuchte Scheitelpunkt w[w]=1;
w=nächster Nachbarpunkt des Scheitelpunkts v
Der Implementierungscode lautet wie folgt:
package com.teradata.lsw.sort;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class BFS {//Storage node information private Object[] vertices;//Speicherkanteninformationsarray private int[][] arcs;//Anzahl der Kanten private int vexnum;// Zeichnen Sie auf, ob der i-te Knoten besucht wurde private boolean[] besuchte;//Erstellen Sie eine temporäre verknüpfte Liste, um die Knoten zu speichern, die durchlaufen wurden private List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO Automatisch generierte Methode stubBFS g = new BFS(8);Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };g.addVertex(vertices);g.addEdge(0, 1);g .addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(3, 5);g.addEdge(4, 5);g.addEdge(2, 6);g.addEdge(2, 7);System.out.println("Breadth-first Traversal des Graphen:");g.bfs();}//Breadth- erste Traversal-Implementierung private void bfs() {// TODO Automatisch generierte Methode stubfor (int i = 0; i < vexnum; i++) {visited[i] = false;}Queue<Integer> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i );q.add(i);while (!q.isEmpty()) {int j = (Integer) q.remove().intValue();//Beurteilen Sie, dass, wenn alle Durchläufe abgeschlossen sind, keine Schleife erforderlich ist if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = this.firstAdjVex(j); k >= 0; k = this.nextAdjVex(j, k)) {if (!visited[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// Finden Sie den nächsten Knoten public int firstAdjVex(int i) {for (int j = 0; j < vexnum ; j++) {if (arcs[i][j] > 0)return j;}return -1;}public int nextAdjVex(int i, int k) {for (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}//Initialisiere die Kanten des Diagramms private void addEdge(int i, int j) {/ / TODO Automatisch generierte Methode stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// Initialisieren Sie die Knoten des Diagramms private void addVertex(Object[] object) {// TODO Automatisch generierte Methode stubthis.vertices = object;}// Initialisieren Sie das Diagramm public BFS(int n) {// TODO Automatisch generierter Konstruktor stubvexnum = n ;vertices = new Object[n];arcs = new int[n][n];visited = new boolean[n];for (int i = 0; i < vexnum; i++) {for (int j = 0; j < vexnum; j++) {arcs[i][j] = 0;}}}private void visit(int i) {// TODO Automatisch generierte Methode stubtemp .add(vertices[i]);System.out.print(vertices[i] + " ");}}