O exemplo neste artigo descreve como Java implementa travessia em largura (BFS) para calcular o caminho mais curto. Compartilhe com todos para sua referência. A análise específica é a seguinte:
Usamos strings para representar o vértice do gráfico para simular as localizações da sala de aula, praça, banheiro, cantina, portão sul e portão norte na escola e, em seguida, calculamos o caminho mais curto entre quaisquer dois pontos.
Conforme mostrado abaixo:
Por exemplo, se eu quiser ir do Portão Norte até a Cantina, o resultado do programa deverá ser:
BFS: De [Portão Norte] a [Cantina]:Portão NorteSquareCanteen
Primeiro defina um algoritmo de interface de algoritmo:
public interface Algorithm { /** * Execute o algoritmo*/ void perform(Graph g, String sourceVertex /** * Obtenha o caminho*/ Map<String, String> getPath();}Em seguida, defina o gráfico:
/** * (não direcionado) gráfico*/public class Graph { // O ponto inicial do gráfico private String firstVertax // Lista de adjacências private Map<String, List<String>> adj = new HashMap<>(); / Algoritmo de travessia algoritmo privado Algoritmo; public Graph(Algoritmo algoritmo) { this.algorithm = algoritmo } /** * Execute o algoritmo*/ public void done() { algoritmo.perform(this, firstVertax); } /** * Obtenha o caminho mais curto do ponto inicial até o ponto {@code vertex} * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack< >() ; stack.add(vértice); Mapa<String, String> caminho = algoritmo.getPath(); ; location = path.get(location)) { stack.push(location } stack.push(firstVertax } /** * Adicionar uma borda*/ public void addEdge(String fromVertex, String toVertex) { if (firstVertax == null) { firstVertax = fromVertex } adj.get(fromVertex).add(toVertex); } /** * Adicionar um vértice*/ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>() } public Map<String, List<String>> getAdj() { return adj; }}Aqui usamos o padrão de design estratégico para separar o algoritmo da classe Graph e selecionamos o algoritmo de travessia para o Graph passando uma implementação da interface Algorithm ao construir o objeto Graph.
gráfico público (algoritmo algoritmo) { this.algorithm = algoritmo };A estrutura de armazenamento do gráfico não direcionado é uma lista de adjacências. Aqui, um mapa é usado para representar a lista de adjacências. A chave do mapa é a localização da escola (String) e o valor é uma lista de localizações (List<String>). conectado ao local.
// Lista de adjacências private Map<String, List<String>> adj = new HashMap<>();
Em seguida, escreva a implementação BFS da interface do Algoritmo:
/** * Encapsula o algoritmo BFS*/public class BroadFristSearchAlgorithm implements Algorithm { // Salva os locais visitados private List<String> visitadoVertex // Salva o caminho mais curto private Map<String, String> path; g, String sourceVertex) { if (null == visitadoVertex) { visitadoVertex = new ArrayList<>() } if (null == caminho) { caminho = new HashMap<>(); } BFS(g, sourceVertex } @Override public Map<String, String> getPath() { return path } private void BFS(Graph g, String sourceVertex) { Queue<String> queue = new LinkedList<>(); // Marca o ponto de partida visitadoVertex.add(sourceVertex); // Enfileira o ponto de partida queue.add(sourceVertex); queue.isEmpty()) { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); v)) { visitadoVertex.add(v); caminho.put(v, ver); fila.add(v);Entre eles, path é do tipo Map, o que significa um caminho do valor até a chave.
Descrição do algoritmo BFS:
1. Marcar a origem como visitada e colocá-la na fila.
2. Pegue um vértice da fila e conecte todos os vértices a ele.
3. Percorra esses vértices, primeiro determine se o vértice foi visitado, caso contrário, marque o ponto como visitado, registre o caminho atual e enfileire o vértice atual.
4. Repita as etapas 2 e 3 até que a fila esteja vazia.
Caso de teste:
String[] vertex = {"Portão Norte", "Portão Sul", "Sala de Aula", "Praça", "Banheiro", "Cantina"}; ), new Edge("Portão Norte", "Quadrado"), new Edge("Sala de Aula", "Banheiro"), novo Edge("Quadrado", "Banheiro"), novo Edge("Quadrado", "Cantina"), new Edge("Banheiro", "Portão Sul"), new Edge("Banheiro", "Portão Sul"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); addEdge(g); g.done(); System.out.println("BFS: De [Portão Norte] para [Cantina]:"); while (!result.isEmpty()) { System.out.println(result.pop());Espero que este artigo seja útil para a programação Java de todos.