El ejemplo de este artículo describe cómo Java implementa el recorrido en amplitud (BFS) para calcular la ruta más corta. Compártelo con todos para tu referencia. El análisis específico es el siguiente:
Usamos cadenas para representar el vértice del gráfico para simular las ubicaciones del aula, la plaza, el baño, el comedor, la puerta sur y la puerta norte en la escuela, y luego calculamos el camino más corto entre dos puntos cualesquiera.
Como se muestra a continuación:
Por ejemplo, si quiero ir de North Gate a Canteen, el resultado del programa debería ser:
BFS: De [Puerta Norte] a [Cantina]:Puerta NorteSquareCantina
Primero defina una interfaz de algoritmo Algoritmo:
Algoritmo de interfaz pública { /** * Ejecutar el algoritmo*/ void perform(Graph g, String sourceVertex /** * Obtener la ruta*/ Map<String, String> getPath();}Luego, define la gráfica:
/** * (No dirigido) gráfico*/public class Graph { // El punto de partida del gráfico private String firstVertax // Lista de adyacencia private Map<String, List<String>> adj = new HashMap<>(); / Algoritmo transversal algoritmo de algoritmo privado; gráfico público (algoritmo de algoritmo) { this.algorithm = algoritmo } /** * Ejecutar el algoritmo*/ public void done() { algoritmo.perform(this, firstVertax); } /** * Obtener la ruta más corta desde el punto inicial hasta el punto {@code vertex} * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack< >() ; stack.add(vértice); Mapa<Cadena, Cadena> ruta = algoritmo.getPath(); ubicación de cadena = ruta.get(vértice); false == ubicación.equals(firstVertax) ; ubicación = ruta.get(ubicación)) { stack.push(ubicación); } stack.push(firstVertax return stack } /** * Agregar un borde*/ public void addEdge(String fromVertex, String toVertex) { if (firstVertax == null) { firstVertax = fromVertex } adj.get(fromVertex).add(toVertex); } /** * Agregar un vértice*/ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>() } public Map<String, List<String>> getAdj() { return adj; }}Aquí usamos el patrón de diseño estratégico para separar el algoritmo de la clase Graph y seleccionamos el algoritmo transversal para Graph pasando una implementación de la interfaz Algorithm al construir el objeto Graph.
Gráfico público (algoritmo algoritmo) { this.algorithm = algoritmo }La estructura de almacenamiento del gráfico no dirigido es una lista de adyacencia. Aquí, se utiliza un mapa para representar la lista de adyacencia. La clave del mapa es la ubicación de la escuela (Cadena) y el valor es una lista de ubicación (Lista <Cadena>). conectado con la ubicación.
// Lista de adyacencia private Map<String, List<String>> adj = new HashMap<>();
Luego, escriba la implementación BFS de la interfaz del algoritmo:
/** * Encapsula el algoritmo BFS*/public class BroadFristSearchAlgorithm implements Algorithm { // Guardar las ubicaciones visitadas private List<String> wantedVertex // Guardar la ruta más corta private Map<String, String> path @Override public void perform( Graph; g, String sourceVertex) { if (nulo == visitedVertex) { visitedVertex = new ArrayList<>() } if (nulo == ruta) { ruta =; new HashMap<>() } BFS(g, sourceVertex); } @Override public Map<String, String> getPath() { ruta de retorno } private void BFS(Graph g, String sourceVertex) { Queue<String> cola = new LinkedList<>(); // Marcar el punto de inicio visitadoVertex.add(sourceVertex); // Poner en cola el punto de inicio queue.add(sourceVertex); queue.isEmpty()) { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); v)) { visitedVertex.add(v); ruta.put(v, ver); cola.add(v);Entre ellos, la ruta es del tipo Mapa, lo que significa una ruta desde el valor hasta la clave.
Descripción del algoritmo BFS:
1. Marca el origen como visitado y ponlo en la cola.
2. Tome un vértice de la cola y conecte todos los vértices al vértice.
3. Atraviese estos vértices, primero determine si el vértice ha sido visitado; de lo contrario, marque el punto como visitado, registre la ruta actual y ponga en cola el vértice actual.
4. Repita los pasos 2 y 3 hasta que la cola esté vacía.
Caso de prueba:
String[] vértice = {"Puerta Norte", "Puerta Sur", "Aula", "Plaza", "Baño", "Cantina" Borde[] bordes = { nuevo Borde("Puerta Norte", "Aula" ), nuevo borde("Puerta Norte", "Cuadrado"), nuevo borde("Aula", "Retrete"), nuevo borde("Cuadrado", "Retrete"), nuevo borde("Cuadrado", "Cantina"), new Edge("Baño", "Puerta Sur"), new Edge("Baño", "Puerta Sur"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); addEdge(g); g.done(); Stack<String> resultado = g.findPathTo("Cantina"); System.out.println("BFS: De [Puerta Norte] a [Cantina]:"); while (!result.isEmpty()) { System.out.println(result.pop());Espero que este artículo sea útil para la programación Java de todos.