Pour comprendre le problème de 15puzes, j'ai appris la recherche en profondeur et la recherche en profondeur. Discutons d'abord de la recherche en profondeur (DFS). Le but de la profondeur d'abord est de hiérarchiser la recherche de chemins les plus éloignés du sommet de départ, tandis que l'étendue-recherche est de rechercher d'abord des chemins les plus proches du sommet de départ. Je me demande quelle est la différence entre la recherche en profondeur d'abord et le retour en arrière? Sur Baidu, il est dit que le retour en arrière est une sorte de recherche profonde, mais la différence est que le retour en arrière ne conserve pas l'arbre de recherche. Alors, qu'en est-il de la recherche de large et de la recherche (BFS)? Quelles sont ses applications? Réponse: Le chemin le plus court, le problème de la division du vin, huit problèmes numériques, etc. Revenons au point, ici, j'ai simplement implémenté une large recherche et une recherche profonde à l'aide de Java. Parmi eux, Deep Search est implémenté à l'aide de Graph + Stack, et une recherche large est implémentée à l'aide de Graph + Fitre. Le code est le suivant:
1. Créez une nouvelle classe NoderectionGraph représentant "Graphique non dirigé"
package com.wly.algorithmbase.datastructure; / ** * graphique non dirigée * @author wly * * / classe publique nodirectiongraph {private int mmaxsize; // le nombre maximum de sommets contenus dans le graphique privé graphvertex [] vertexList; // l'indicateur de connexion entre la connexion entre la relation privée [] [] indicate; // Adjacent Matrix. private int nvertex; // le nombre de sommets actuellement enregistrés publiques nodirectiongraph (int maxsize) {mmaxsize = maxsize; vertexList = new graphvertex [mmaxsize]; indicatormat = new int [mmaxSize] [mmaxsize]; nvertex = 0; // initialiser l'élément matelle adjacency j = 0; j <mmaxsize; j ++) {for (int k = 0; k <mmaxsize; k ++) {indicatormat [j] [k] = 0;}}} public void addvertex (graphvertex v) {if (nvertex <mmaxsize) {vertexList [nvertex ++] = V;} {System.out.println ("--- Échec de l'insertion, le nombre de sommets a atteint la limite supérieure!");}} / ** * Modifier la matrice d'adjacence et ajouter un nouveau bord * @param start * @param end * / public void Addge (int start, int fin) {indicatormat [start] [end] = 1; Matrice d'adjacence * / public void printIndicatOrmat () {for (int [] line: indicatormat) {for (int i: line) {System.out.print (i + "");} system.out.println ();}} / ** * Depth Priority Traversal * @param vertexindex Matrice du graphique * / public void dfs (int vertexIndex) {arraystack stack = new ArrayStack (); // 1. Ajoutez l'élément de recherche à la pile vertexlist [vertexIndex] .SetVisited (true); stack.push (vertexIndex); int nextVerTexIndex = getNextVerTexIndex (vertexIndex); while (! stack.isempty ()) {// Appuyez en continu la pile et sortez la pile jusqu'à ce que la pile soit vide (l'élément de recherche n'apparaît pas la pile) if (nextVertexIndex! = -1) {vertexList [NextVertexIndex]. {stack.pop ();} // Récupère si l'élément supérieur actuel contient d'autres nœuds non trahison getNextverTexIndex (int colonnel) {for (int i = 0; i <indicatormat [colonne] .length; i ++) {if (indicatormat [colonne] [i] == 1 &&! vertexlist [i] .isvisite traverse, that is, the number of rows in the adjacency matrix of the graph*/public void BFS(int vertexIndex) {ChainQueue queue = new ChainQueue();vertexList[vertexIndex].setVisited(true);queue.insert(new QueueNode(vertexIndex));int nextVertexIndex = getNextVertexIndex(vertexIndex); while (! queue.isempty ()) {if (nextVertexIndex! = -1) {vertexList [NextVertexIndex] .SetVisite getNExtverTexIndex (queue.Peek (). Data); queue.printelems ();}}}}2. Ensuite, il y a un tableau qui est simulé avec un tableau
Package com.wly.algorithmbase.datastructure; / ** * Utilisez des tableaux pour implémenter la structure de la pile * @Author wly * * / classe publique ArrayStack {private int [] tarray; private int topindex = -1; // indique la position d'index de l'élément supérieur actuel de la pile private {) array *** / tarray = new int [capacity_step];} / ** * Méthode pour faire apparaître l'élément supérieur * @return * / public int pop () {if (isempty ()) {System.out.println ("Erreur, l'élément dans la pile est vide, ne peut pas pop"); return -1;} else {int i = tarray [topindex]; tarray [topindex--] = -1; // efface l'élément pop return i;}} / ** * insérer un élément dans la pile * @param t * / public void push (int t) {// vérifie si la pile est complète si (topindex == (tarray.Legth-1)) {// prolonger la capacité int [] Temps == (Tarray.Legth-1)) {// extenger la capacité int [] Temps == (Tarray.Legth-1)) {// Expulsion CACHITE IF (TOPIDEX == (Tarray.Legth-1)) {// Expulsion CACHITE IF (TOPIDEX == (Tarray.Legth-1)) {// Expulsion CACHITE CONTACTY int [tarray.length + capacity_step]; pour (int i = 0; i <tarray.length; i ++) {temparray [i] = tarray [i];} tarray = temparray; temparray = null;} else {topindex ++; tarray [topindex] = t;}} / ** * obtenir l'élément supérieur de la pile, mais ne fait pas up up * @return * / public int pek {if (isEmpty ()) {System.out.println ("Erreur, l'élément dans la pile est vide, ne peut pas voir"); return -1;} else {return tarray [topindex];}} / ** * Vérifiez si la pile actuelle est vide * @return * / public boolean isEmpty () {return (topindex <0);} / ** * elees * / Public pile printElems () {for (int i = 0; i <= topindex; i ++) {System.out.print (tarray [i] + "");} System.out.println ();}}3. Chainqueue dans une file d'attente simulée avec des listes liées
package com.wly.algorithmbase.datastructure; / ** * Utilisez la liste liée pour implémenter la file d'attente * * @author wly * * / classe publique chainqueue {private queuenode head; // pointer vers la tête de la file d'attente Private Queuenode Tail; // pointer vers la queue de la file d'attente private intze = 0; // que la queue de la queue de la queue de la file d'attente * / insert public public (Node Qu queuenode) {// Bien sûr, vous pouvez également écrire ceci, ajouter tail.prev = node if (head == null) {head = node; tail = head;} else {node.next = tail; tail.prev = node; // bidirectional connection pour assurer que la tête. Le nœud de tête de file d'attente * / public queuenode retira () {if (! isempty ()) {Queuenode temp = head; head = head.prev; size -; return temp;} else {System.out.println ("opération exception, la file d'attente actuelle est vide!"); retour null;}} / ** * est la file d'attente vide * * @return * / public boolean estmpy () est la file d'attente * (taille> 0) {return false;} else {return true;}} / ** * return le premier nœud de la file d'attente, mais pas de supprimer * / return queuenode peek () {if (! isEmpty ()) {return Head;} else {System.out.println (); System.out.println ("Exception, l'exception, la file d'attente actuelle est vide!"); Renvoie la taille de la file d'attente * * @return * / public int size () {return size;} / ** * imprimer des éléments dans la file d'attente * / public void printElems () {queuenode tempnode = head; while (tempnode! = Null) {System.out.print (tempnode.data + ""); tempnode = tempnode.prev;} System.out.println ();}} / ** * classe de nœuds * * @author wly * * / class queuenode {queuenode préc; Queuenode Next; int data; public queuenode (int data) {this.data = data;} public int GetData () {return data {this.data = data;} @ override public String toString () {// Todo Méthode générée auto4. test test_bfs_dfs
Package com.wly.algorithmbase.search; import com.wly.algorithmbase.datastructure.graphvertex; import com.wly.algorithmbase.datastructure.nodirectiongraph; / ** * Recherche de profondeur de graphisme {// Initialiser les données de test NoderectionGraph graphique = new NoderectionGraph (7); graph.addvertex (new Graphvertex ("a")); graph.addvertex (new Graphvertex ("B")); Graph.Addvertex (New Graphvertex ("C")); Graph.Addverx (New Graphvertex ("D")); Addvertex (New Graphvertex ("D")); GraphVertex ("E")); Graph.AddverTex (New GraphverTex ("F")); Graph.Addvertex (new GraphverTex ("G")); Graph.AdDedge (0, 1); Graph.AdDedge (0, 2); Graph.Addedge (1, 3); Graph.AdDedge (1, 4); Graph.AdDedge (3, 6); 5); System.out.println ("- Matrice adjacente du graphique -"); graph.printIndicatOrmat (); // Tester Deep Search System.out.println ("- Deep Priority Search -"); graph.dfs (0); Graph = New NoderectionGraph (7); Graph.Addvertex (New GraphVertex ("A"); GraphVertex ("B")); Graph.AddverTex (new GraphverTex ("C")); Graph.Addvertex (new GraphVertex ("D")); Graph.Addvertex (new GraphVertex ("E")); Graph.Addvertex (new GraphverTex ("F")); Graph.Addvertex (new GraphverTex ("g")); graph.adDedge (0, 1); graph.adDedge (0, 2); graph.adDedge (1, 3); graph.addedge (1, 4); graph.addedge (3, 6); graph.adDedge (2, 5); System.out.println ("- Search priority Search -"); Graph.bfs (0);La structure du graphique testée ici est la suivante:
Les résultats de l'opération sont les suivants:
- Matrice adjacent du graphique - 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Ici, nous devons expliquer les résultats en cours d'exécution d'une recherche profonde et d'une recherche large ci-dessus, où 0, 1, 2, 3 ... correspond à A, B, C, D respectivement ... c'est un peu déroutant, veuillez me pardonner ~~
Oh ~~~
Résumer
Ce qui précède est tout le contenu de cet article sur la mise en œuvre de la programmation Java de la recherche en profondeur basée sur les graphiques et de l'étendue de recherche complète du code complet. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!