Чтобы понять проблему 15Pulzzle, я узнал о поиске по глубине и поиску в ширину. Давайте сначала обсудим поиск по глубине (DFS). Целью глубины является то, чтобы определить приоритеты в поиске путей, которые являются самыми дальним от начальной вершины, в то время как поиск в ширине-сначала поиск путей, которые наиболее близки к начальной вершине. Интересно, в чем разница между поиском глубины и возвратом? На Baidu говорят, что отступление - это своего рода глубокий поиск, но разница в том, что отступление не сохраняет дерево поиска. Так что насчет поиска в области широты (BFS)? Каковы его приложения? Ответ: самый короткий путь, проблема с подразделением вина, восемь цифровых проблем и т. Д. Давайте вернемся к делу, здесь я просто реализовал широкий поиск и глубокий поиск с использованием Java. Среди них глубокий поиск реализуется с использованием Graph + Stack, а широкий поиск реализуется с использованием очереди Graph +. Код заключается в следующем:
1. Создайте новый класс NodirectionGraph, представляющий «Недоставленный график»
Пакет com.wly.algorithmbase.datastructure;/** * undered Graph * @author wly * */public class nodirectiongraph {private int mmaxsize; // Максимальное количество вершин, содержащихся в графике private graphvertex [] vertexlist; // vertex rative private int [] indatorment; private int nvertex; // Количество вершин, сохранившихся в настоящее время, общедоступной nodirectiongraph (int maxsize) {mmaxsize = maxsize; vertexlist = new Graphvertex [mmaxsize]; indicatormat = new int [mmaxsize] [mmaxsize]; nvertex = 0;/инициализируйте letracency matrix для 0 nvertex = 0; j = 0; j <mmaxsize; j ++) {for (int k = 0; k <mmaxsize; k ++) {indicatormat [j] [k] = 0;}}} public addvertex (graphvertex v) {if (nvertex <mmaxsize) {vertexlist [nvertex+v; {System.out.println ("--- Не удалось ввести, количество вершин достигло верхнего предела!");}}/*** Модифицировать матрицу смежности и добавить новый край* @param start* @param end*/public addedde Матрица смежности*/public void printIndicatormat () {for (int [] line: indicatormat) {for (int i: line) {System.out.print (i + "");} system.out.println ();}}/*** Глубина Матрица графика */public void dfs (int vertexindex) {arraystack stach = new ArrayStack (); // 1. Добавить элемент поиска в стек Vertexlist [vertexindex] .setVisited (true); Stack.push (vertexindex); int nextvertexindex = getNextVertexIndex (VertexIndex); while (! stack.isempty ()) {// Непрерывно нажимайте стек и из стека, пока стек не станет пустым (элемент поиска не всплывает в стеке) if (NextvertexIndex! = -1) {vertexlist [nextvertexIndex] .setVisted (true); Stack.push (NextvertexIndex); printelem. Текущий топ -элемент содержит другие нетронутые узлы if (! Stack.isempty ()) {NextVertexIndex = getNextVertexIndex (stack.peek ());}}}/** * Получить строку, где следующая вершина текущей вершины (столбец int (int int (int) {int) {int) {int) {int) {int) {int (int) {int) {int) {int) {int) {int) {int) {int) {int) {int) {int) {int) {int) {@param * @return i = 0; i <indicatormat [column] .length; i ++) {if (indicatormat [column] [i] == 1 &&! vertexlist [i] .isvisited ()) {return i;}} возвращать -1;}/*** График*/public void bfs (int vertexindex) {queue Queue = new Cheatqueue (); Vertexlist [VertexIndex] .setVisited (true); queue.insert (new queuenode (vertexindex)); int stembertexindex = getNextVertexIndex (vertexIndex); while (! queue.isempty ()) {if (NextVertexIndex! = -1) {vertexlist [NextVertexIndex] .setSited (true); queue.insert (new queuenode (NextVertexIndex);} else {Queue.Remove (); if (! getNextVertexIndex (queue.peek (). data); queue.printelems ();}}}}2. Тогда есть ArrayStack, который моделируется с помощью массива
пакет com.wly.algorithmbase.datastructure;/***Используйте массивы для реализации структуры стека*@author wly**/public class arraystack {private int [] tarray; private int topeNdex = -1; // Установите положение индекса текущего верхнего элемента стека Private емко Generic Array ***/tarray = new int [apip_step];}/***Метод для появления верхнего элемента*@return*/public int pop () {if (isempty ()) {System.out.println («Ошибка, элемент в стеке пуст, не может всплыть»); return -1;} else {int i = tarray [topeNdex]; tarray [topeNdex--] = -1; // Смоскате element pop i;}}/*** Вставить элемент в стек* @param t*/public void push (int t) {// проверьте, является ли стек. int [tarray.length + емкость_step]; for (int i = 0; i <tarray.length; i ++) {temparray [i] = tarray [i];} tarray = temparray; temparray = null;} else {topeNdex ++; tarray [topeNdex] = t;}}/** * Получить верхний элемент стека, но не всплыл * @return */**. {System.out.println («Ошибка, элемент в стеке пуст, не может быть заглянуть»); return -1;} else {return tarray [topeNdex];}}/*** Проверьте, является ли текущий стек пустым* @return*/public boolean isempty () {return (topindex <0);}/** elements in anements in stack*/videm printem (inter printem i = 0; i <= topeNdex; i ++) {System.out.print (tarray [i]+"");} System.out.println ();}}3. Cheanqueue в очереди, смоделированном с связанными списками
пакет com.wly.algorithmbase.datastructure;/** * Используйте связанный список для реализации очереди * * @author wly * */public class chainqueue {private Queuenode Head; // указывать на голову Queue Private Queuenode Hail; // указывать на хвост Queue Private Sreate = 0; // Queue public quipt queptae (). Новый узел к хвосту очереди*/public void вставка (Queuenode Node) {// Конечно, вы также можете написать это, добавить tail.prev = node if (head == null) {head = node; hail = head;} els node;} size ++;}/*** Удалить узлом головки очередей*/public Queuenode remove () {if (! isempty ()) {queuenode temp = head; head = head.prev; size-; return temp;} else {system.out.println ("Операция исключения, ток, не пустая!") * @return */public boolean isempty () {if (size> 0) {return false;} else {return true;}}/** * Возвращает первый узел очереди, но не удалить */public queuenode peek () {if (! isempty ()) {return head; {system.out.print.println () system. Очередь пуста! "); return null;}}/*** возвращает размер очереди** @return*/public int size () {return size;}/*** Элементы печати в очереди*/public void printelems () {queuenode tempnode = head; while (tempnode! tempnode.prev;} system.out.println ();}}/** * класс узла * * @author wly * */class queuenode {queuenode prev; queuenode Далее; int data; public queuenode (int data) {this.data = data;} public getData () {return Data) at.at Data) {this.data = data;}@переопределить публичную строку toString () {// todo автоматически генерируется на stub super.tostring (); return data + "";}}4. test test_bfs_dfs
пакет com.wly.algorithmbase.search; import com.wly.algorithmbase.datastructure.graphvertex; import com.wly.algorithmbase.datastructure.nodirectiongraph;/** * На основе графика первого поиска * @author wly * */public class test_bfs_df {stics restics {stics restics restics {strics resmor wrys resmor) {// Инициализировать тестовые данные nodirectiongraph Graph = new nodirectiongraph (7); graph.addvertex (new Graphvertex ("a")); graph.addvertex (new Graphvertex ("b")); graph.addvertex (new Graphvertex ("c")); graph.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); 5); System.out.println ("-соседняя матрица графика-"); graph.printindicatormat (); // test Deep Search System.out.println ("-Глубокий приоритетный поиск-"); graph.dfs (0); graph = new nodirectiongraph (7); graph.addvertex (new Graphverex ("a"); Graphvertex ("b")); graph.addvertex (new Graphvertex ("c")); graph.addvertex (new Graphvertex ("d")); graph.addvertex (new graphvertex ("e"); 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 ("-Приоритетный поиск-");Структура графика, проверенная здесь, следующая:
Результаты работы следующие:
—Аdjacent Матрица графика-0 1 1 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 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 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 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 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 0
Здесь нам нужно объяснить результаты выполнения глубокого поиска и широкого поиска выше, где 0, 1, 2, 3 ... соответствует A, B, C, D соответственно ... это немного запутанно, пожалуйста, простите меня ~~
О ~~~
Суммировать
Выше приведено все содержимое этой статьи о реализации программирования Java программирования на графике, основанном на глубине, и полном поиске в ширине. Я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это. Спасибо, друзья, за вашу поддержку на этом сайте!