L'exemple de cet article décrit comment Java implémente le parcours en largeur en premier (BFS) pour calculer le chemin le plus court. Partagez-le avec tout le monde pour votre référence. L’analyse spécifique est la suivante :
Nous utilisons des chaînes pour représenter le sommet du graphique afin de simuler les emplacements de la salle de classe, de la place, des toilettes, de la cantine, de la porte sud et de la porte nord de l'école, puis calculons le chemin le plus court entre deux points.
Comme indiqué ci-dessous :
Par exemple, si je veux passer de North Gate à Canteen, le résultat du programme devrait être :
BFS : De [Porte Nord] à [Cantine] : Porte NordSquareCantine
Définissez d’abord un algorithme d’interface Algorithme :
public interface Algorithm { /** * Exécuter l'algorithme*/ void perform(Graph g, String sourceVertex /** * Récupérer le chemin*/ Map<String, String> getPath();}Ensuite, définissez le graphique :
/** * (Non dirigé) graph*/public class Graph { // Le point de départ du graphique private String firstVertax; // Liste de contiguïté private Map<String, List<String>> adj = new HashMap<>(); / Algorithme de traversée Algorithme privé Algorithme ; public Graph(Algorithm algorithm) { this.algorithm = algorithm; } /** * Exécuter l'algorithme*/ public void done() { algorithm.perform(this, firstVertax); } /** * Récupère le chemin le plus court du point de départ au point {@code vertex} * @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); return stack; /** * Ajouter un bord*/ public void addEdge(String fromVertex, String toVertex) { if (firstVertax == null) { firstVertax = fromVertex } adj.get(fromVertex).add(toVertex); } /** * Ajouter un sommet*/ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>()); public Map<String, List<String>> getAdj() { return adj; }}Ici, nous utilisons le modèle de conception stratégique pour séparer l'algorithme de la classe Graph et sélectionnons l'algorithme de parcours pour le Graph en passant une implémentation de l'interface Algorithm lors de la construction de l'objet Graph.
public Graph (algorithme d'algorithme) { this.algorithm = algorithme }La structure de stockage du graphique non orienté est une liste de contiguïté.Ici, une carte est utilisée pour représenter la liste de contiguïté. La clé de la carte est l'emplacement de l'école (String) et la valeur est une liste d'emplacements (List<String>). connecté à l'emplacement.
// Liste de contiguïté private Map<String, List<String>> adj = new HashMap<>();
Ensuite, écrivez l'implémentation BFS de l'interface Algorithm :
/** * Encapsule l'algorithme BFS*/classe publique BroadFristSearchAlgorithm implémente l'algorithme { // Enregistre les emplacements visités private List<String> visitVertex; // Enregistre le chemin le plus court private Map<String, String> path; @Override public void perform( Graph) g, String sourceVertex) { if (null == visitVertex) { visitVertex = new ArrayList<>( } if (null == chemin) { chemin = new HashMap<>(); } BFS(g, sourceVertex); } @Override public Map<String, String> getPath() { chemin de retour } private void BFS(Graph g, String sourceVertex) { Queue<String> queue = new LinkedList<>(); // Marque le point de départ visitVertex.add(sourceVertex); // Met en file d'attente le point de départ queue.add(sourceVertex); queue.isEmpty()) { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); for (String v : toBeVisitedVertex) { if (false == visitVertex.contains( v)) { visitVertex.add(v); path.put(v, ver);Parmi eux, path est un type Map, ce qui signifie un chemin allant de la valeur à la clé.
Description de l'algorithme BFS :
1. Marquez l'origine comme visitée et mettez-la dans la file d'attente.
2. Prenez un sommet de la file d’attente et récupérez tous les sommets connectés au sommet.
3. Parcourez ces sommets, déterminez d'abord si le sommet a été visité, sinon, marquez le point comme visité, enregistrez le chemin actuel et mettez le sommet actuel en file d'attente.
4. Répétez les étapes 2 et 3 jusqu'à ce que la file d'attente soit vide.
Cas de test :
String[] vertex = {"Porte Nord", "Porte Sud", "Salle de classe", "Carré", "Toilette", "Cantine"}; Edge[] bords = { new Edge("Porte Nord", "Salle de classe" ), new Edge("Porte Nord", "Carré"), new Edge("Salle de classe", "Toilettes"), new Edge("Carré", "Toilettes"), new Edge("Carré", "Cantine"), new Edge("Toilette", "Porte Sud"), new Edge("Toilette", "Porte Sud"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); addEdge(g); g.done(); Stack<String> result = g.findPathTo("Cantine"); System.out.println("BFS : De [Porte Nord] à [Cantine] :"); while (!result.isEmpty()) { System.out.println(result.pop() } );J'espère que cet article sera utile à la programmation Java de chacun.