To understand the 15puzzle problem, I learned about depth-first search and breadth-first search. Let’s first discuss depth-first search (DFS). The purpose of depth-first is to prioritize searching for paths that are farthest from the starting vertex, while breadth-first searching is to first searching for paths that are closest to the starting vertex. I wonder what is the difference between depth-first search and backtracking? On Baidu, it is said that backtracking is a kind of deep search, but the difference is that backtracking does not retain the search tree. So what about Broadness-first search (BFS)? What are its applications? Answer: The shortest path, wine division problem, eight digital problem, etc. Let’s get back to the point, here I have simply implemented broad search and deep search using Java. Among them, deep search is implemented using graph + stack, and broad search is implemented using graph + queue. The code is as follows:
1. Create a new class NoDirectionGraph representing "undirected graph"
package com.wly.algorithmbase.datastructure;/** * Undirected graph* @author wly * */public class NoDirectionGraph {private int mMaxSize;//The maximum number of vertices contained in the graph private GraphVertex[] vertexList;//The vertex array private int[][] indicatorMat;//Adjacent matrix indicating the connection relationship between vertices private int nVertex;//The number of vertices currently saved public NoDirectionGraph(int maxSize) {mMaxSize = maxSize;vertexList = new GraphVertex[mMaxSize];indicatorMat = new int[mMaxSize][mMaxSize];nVertex = 0;//Initialize the adjacency matrix element to 0 for (int 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;} else {System.out.println("---Insertion failed, the number of vertices has reached the upper limit!");}}/** * Modify the adjacency matrix and add a new edge* @param start * @param end */public void addEdge(int start,int end) {indicatorMat[start][end] = 1;indicatorMat[end][start] = 1;}/** * Print the adjacency matrix*/public void printIndicatorMat() {for (int[] line:indicatorMat) {for (int i:line) {System.out.print(i + " ");}System.out.println();}}/** * Depth priority traversal* @param vertexIndex Index represents the starting point to traverse, that is, the number of rows in the adjacency matrix of the graph */public void DFS(int vertexIndex) {ArrayStack stack = new ArrayStack();//1. Add the search element to the stack vertexList[vertexIndex].setVisited(true);stack.push(vertexIndex);int nextVertexIndex = getNextVertexIndex(vertexIndex); while(!stack.isEmpty()) {//Continuously press the stack and out the stack until the stack is empty (the search element does not pop up the stack) if(nextVertexIndex != -1) {vertexList[nextVertexIndex].setVisted(true);stack.push(nextVertexIndex);stack.printElems();} else {stack.pop();}//Retrieve whether the current top element contains other untraversed nodes if(!stack.isEmpty()) {nextVertexIndex = getNextVertexIndex(stack.peek());}}}/** * Get the line where the next vertex of the current vertex is located* @param column * @return */public int getNextVertexIndex(int column) {for (int i=0;i<indicatorMat[column].length;i++) {if(indicatorMat[column][i] == 1 && !vertexList[i].isVisited()) {return i;}}return -1;}/** * Breadth-first traversal* @param vertexIndex represents the starting point to 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].setVisited(true);queue.insert(new QueueNode(nextVertexIndex));} else {queue.remove();}if(!queue.isEmpty()) {nextVertexIndex = getNextVertexIndex(queue.peek().data);queue.printElems();}}}}2. Then there is an ArrayStack that is simulated with an array
package com.wly.algorithmbase.datastructure;/** * Use arrays to implement stack structure* @author wly * */public class ArrayStack {private int[] tArray;private int topIndex = -1;//Indicate the index position of the current top element of the stack private int CAPACITY_STEP = 12;//Array capacity expansion step size public ArrayStack() {/***A method to create generic array***/tArray = new int[CAPACITY_STEP];}/** * Method to pop up top element* @return */public int pop() {if(isEmpty()) {System.out.println("Error, the element in the stack is empty, cannot pop"); return -1;} else {int i = tArray[topIndex];tArray[topIndex--] = -1;//Erase the pop element return i;}}/** * Insert an element into the stack* @param t */public void push(int t) {//Check whether the stack is full if(topIndex == (tArray.length-1)) {//Extend capacity int[] tempArray = new int[tArray.length + CAPACITY_STEP]; for (int i=0;i<tArray.length;i++) {tempArray[i] = tArray[i];}tArray = tempArray;tempArray = null;} else {topIndex ++;tArray[topIndex] = t;}}/** * Get the top element of the stack, but does not pop up * @return */public int peek() {if(isEmpty()) {System.out.println("Error, the element in the stack is empty, cannot peek");return -1;} else {return tArray[topIndex];}}/** * Check whether the current stack is empty* @return */public Boolean isEmpty() {return (topIndex < 0);}/** * Elements in the print stack*/public void printElems() {for (int i=0;i<=topIndex;i++) {System.out.print(tArray[i] + " ");}System.out.println();}}3. ChainQueue in a queue simulated with linked lists
package com.wly.algorithmbase.datastructure;/** * Use linked list to implement queue* * @author wly * */public class ChainQueue {private QueueNode head;// point to the head of the queue private QueueNode tail;// point to the tail of the queue private int size = 0;// queue size public ChainQueue() {}/** * Insert a new node to the tail of the queue*/public void insert(QueueNode node) {// Of course, you can also write this, add tail.prev = node if (head == null) {head = node;tail = head;} else {node.next = tail;tail.prev = node;// Bidirectional connection to ensure that head.prev is not empty tail = node;}size++;}/** * Remove the queue head node*/public QueueNode remove() {if (!isEmpty()) {QueueNode temp = head;head = head.prev;size--;return temp;} else {System.out.println("Exception operation, the current queue is empty!");return null;}}/** * Is the queue empty* * @return */public Boolean isEmpty() {if (size > 0) {return false;} else {return true;}}/** * Return the first node of the queue, but not remove */public QueueNode peek() {if (!isEmpty()) {return head;} else {System.out.println();System.out.println("Exception operation, the current queue is empty!");return null;}}/** * Return the queue size* * @return */public int size() {return size;}/** * Print elements in the queue*/public void printElems() {QueueNode tempNode = head;while(tempNode != null) {System.out.print(tempNode.data + " ");tempNode = tempNode.prev;}System.out.println();}}/** * Node class* * @author wly * */class QueueNode {QueueNode prev;QueueNode next;int data;public QueueNode(int data) {this.data = data;}public int getData() {return data;}public void setData(int data) {this.data = data;}@Override public String toString() {// TODO Auto-generated method stub super.toString();return data + "";}}4. Test Test_BFS_DFS
package com.wly.algorithmbase.search;import com.wly.algorithmbase.datastructure.GraphVertex;import com.wly.algorithmbase.datastructure.NoDirectionGraph;/** * Graph-based depth-first search* @author wly * */public class Test_BFS_DFS {public static void main(String[] args) {//Initialize test data 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"));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("--Adjacent Matrix of Graph--");graph.printIndicatorMat();//Test deep search System.out.println("--Deep priority search--");graph.DFS(0);graph = new NoDirectionGraph(7);graph.addVertex(new GraphVertex("A"));graph.addVertex(new 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("--Breadth Priority Search--");graph.BFS(0);}}The graph structure tested here is as follows:
The operation results are as follows:
--Adjacent matrix of graph-- 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 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
Here we need to explain the running results of deep search and broad search above, where 0, 1, 2, 3... corresponds to A, B, C, D respectively... it is a bit confusing, please forgive me~~
Oh~~~
Summarize
The above is all the content of this article about Java programming implementation of graph-based depth-first search and breadth-first search complete code. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!