Das Beispiel in diesem Artikel beschreibt, wie Java die Breitendurchquerung (BFS) implementiert, um den kürzesten Pfad zu berechnen. Teilen Sie es als Referenz mit allen. Die spezifische Analyse lautet wie folgt:
Wir verwenden Zeichenfolgen, um den Scheitelpunkt des Diagramms darzustellen, um die Standorte Klassenzimmer, Platz, Toilette, Kantine, Südtor und Nordtor in der Schule zu simulieren, und berechnen dann den kürzesten Weg zwischen zwei beliebigen Punkten.
Wie unten gezeigt:
Wenn ich beispielsweise vom Nordtor zur Kantine gehen möchte, sollte die Ausgabe des Programms wie folgt aussehen:
BFS: Von [North Gate] nach [Canteen]:North GateSquareCanteen
Definieren Sie zunächst einen Algorithmusschnittstellenalgorithmus:
public interface Algorithm { /** * Algorithmus ausführen*/ void perform(Graph g, String sourceVertex); /** * Pfad abrufen*/ Map<String, String> getPath();}Definieren Sie dann das Diagramm:
/** * (Ungerichteter) Graph*/public class Graph { // Der Startpunkt des Graphen private String firstVertax; // Adjacency list private Map<String, List<String>> adj = new HashMap<>(); / Traversal-Algorithmus privater Algorithmus algorithm; public Graph(Algorithmus algorithm) { this.algorithm = algorithm } /** * Algorithmus ausführen*/ public void done() { algorithm.perform(this, firstVertax); } /** * Den kürzesten Weg vom Startpunkt zum {@code vertex}-Punkt abrufen * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack< >() ; stack.add(vertex); Map<String, String> path = algorithm.getPath(); for (String location = path.get(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) { stack.push(location); } stack.push(firstVertax); if (firstVertax == null) { firstVertax = fromVertex; } adj.get(fromVertex).add(toVertex); } /** * Einen Scheitelpunkt hinzufügen*/ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>() } public Map<String, List<String>> getAdj() { return adj; }}Hier verwenden wir das strategische Entwurfsmuster, um den Algorithmus von der Graph-Klasse zu trennen, und wählen den Traversalalgorithmus für den Graph aus, indem wir beim Erstellen des Graph-Objekts eine Implementierung der Algorithm-Schnittstelle übergeben.
public Graph(Algorithmus algorithm) { this.algorithm = algorithm;Die Speicherstruktur des ungerichteten Diagramms ist eine Adjazenzliste. Hier wird eine Karte verwendet, um die Adjazenzliste darzustellen. Der Schlüssel der Karte ist der Schulstandort (String) und der Wert ist eine Standortliste (List<String>). mit dem Standort verbunden.
// Adjazenzliste private Map<String, List<String>> adj = new HashMap<>();
Schreiben Sie dann die BFS-Implementierung der Algorithmusschnittstelle:
/** * Kapselt den BFS-Algorithmus*/öffentliche Klasse BroadFristSearchAlgorithm implementiert Algorithmus { // Speichere besuchte Orte private List<String> besuchteVertex; // Speichere den kürzesten Pfad private Map<String, String> path; @Override public void perform( Graph g, String sourceVertex) { if (null == besuchteVertex) { besuchteVertex = new ArrayList<>(); } if (null == path) { path = new HashMap<>(); } BFS(g, sourceVertex); } @Override public Map<String, String> { return path; } private void BFS(Graph g, String sourceVertex) { Queue<String> queue = new LinkedList<>(); // Markiere den Startpunkt queue.isEmpty() { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); for (String v : toBeVisitedVertex) { if (false == besuchteVertex.contains( v)) { besuchteVertex.add(v); path.put(v, ver); queue.add(v);Unter diesen ist path ein Map-Typ, also ein Pfad vom Wert zum Schlüssel.
Beschreibung des BFS-Algorithmus:
1. Markieren Sie den Ursprung als besucht und stellen Sie ihn in die Warteschlange.
2. Nehmen Sie einen Scheitelpunkt aus der Warteschlange und rufen Sie alle mit dem Scheitelpunkt verbundenen Scheitelpunkte ab.
3. Durchqueren Sie diese Scheitelpunkte. Stellen Sie zunächst fest, ob der Scheitelpunkt besucht wurde. Wenn nicht, markieren Sie den Punkt als besucht, zeichnen Sie den aktuellen Pfad auf und stellen Sie den aktuellen Scheitelpunkt in die Warteschlange.
4. Wiederholen Sie die Schritte 2 und 3, bis die Warteschlange leer ist.
Testfall:
String[] vertex = {"North Gate", "South Gate", "Classroom", "Square", "Toilet", "Canteen"}; ), new Edge("North Gate", "Square"), new Edge("Classroom", "Toilet"), new Edge("Square", "Toilet"), new Edge("Square", "Kantine"), new Edge("Toilet", "South Gate"), new Edge("Toilet", "South Gate"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); addEdge(g); g.done(); Stack<String> result = g.findPathTo("Canteen"); System.out.println("BFS: From [North Gate] to [Canteen]:"); while (!result.isEmpty()) { System.out.println(result.pop()} }Ich hoffe, dass dieser Artikel für die Java-Programmierung aller hilfreich sein wird.