為了解15puzzle問題，了解了一下深度優先搜索和廣度優先搜索。先來討論一下深度優先搜索(DFS)，深度優先的目的就是優先搜索距離起始頂點最遠的那些路徑，而廣度優先搜索則是先搜索距離起始頂點最近的那些路徑。我想著深度優先搜索和回溯有什麼區別呢？百度一下，說回溯是深搜的一種，區別在於回溯不保留搜索樹。那麼廣度優先搜索(BFS)呢?它有哪些應用呢？答：最短路徑，分酒問題，八數碼問題等。言歸正傳，這裡筆者用java簡單實現了一下廣蒐和深搜。其中深搜是用圖+棧實現的，廣蒐使用圖+隊列實現的，代碼如下：
1.新建一個表示“無向圖”類NoDirectionGraph
package com.wly.algorithmbase.datastructure;/** * 無向圖* @author wly * */public class NoDirectionGraph {private int mMaxSize;//圖中包含的最大頂點數private GraphVertex[] vertexList;//頂點數組private int[][] indicatorMat;//指示頂點之間的連通關係的鄰接矩陣private int nVertex;//當前實際保存的頂點數目public NoDirectionGraph(int maxSize) {mMaxSize = maxSize;vertexList = new GraphVertex[mMaxSize];indicatorMat = new int[mMaxSize][mMaxSize];nVertex = 0;//初始化鄰接矩陣元素為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("---插入失敗，頂點數量已達上限!");}}/** * 修改鄰接矩陣，添加新的邊* @param start * @param end */public void addEdge(int start,int end) {indicatorMat[start][end] = 1;indicatorMat[end][start] = 1;}/** * 打印鄰接矩陣*/public void printIndicatorMat() {for (int[] line:indicatorMat) {for (int i:line) {System.out.print(i + " ");}System.out.println();}}/** * 深度優先遍歷* @param vertexIndex 表示要遍歷的起點,即圖的鄰接矩陣中的行數*/public void DFS(int vertexIndex) {ArrayStack stack = new ArrayStack();//1.添加檢索元素到棧中vertexList[vertexIndex].setVisited(true);stack.push(vertexIndex);int nextVertexIndex = getNextVertexIndex(vertexIndex);while(!stack.isEmpty()) {//不斷地壓棧、出棧，直到棧為空(檢索元素也沒彈出了棧)為止if(nextVertexIndex != -1) {vertexList[nextVertexIndex].setVisited(true);stack.push(nextVertexIndex);stack.printElems();} else {stack.pop();}//檢索當前棧頂元素是否包含其他未遍歷過的節點if(!stack.isEmpty()) {nextVertexIndex = getNextVertexIndex(stack.peek());}}}/** * 得到當前頂點的下一個頂點所在行* @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;}/** * 廣度優先遍歷* @param vertexIndex 表示要遍歷的起點,即圖的鄰接矩陣中的行數*/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.然後是一個用數組模擬的棧ArrayStack
package com.wly.algorithmbase.datastructure;/** * 使用數組實現棧結構* @author wly * */public class ArrayStack {private int[] tArray;private int topIndex = -1;//表示當前棧頂元素的索引位置private int CAPACITY_STEP = 12;//數組容量擴展步長public ArrayStack() {/***創建泛型數組的一種方法***/tArray = new int[CAPACITY_STEP];}/** * 彈出棧頂元素方法* @return */public int pop() {if(isEmpty()) {System.out.println("錯誤，棧中元素為空，不能pop");return -1;} else {int i = tArray[topIndex];tArray[topIndex--] = -1;//擦除pop元素return i;}}/** * 向棧中插入一個元素* @param t */public void push(int t) {//檢查棧是否已滿if(topIndex == (tArray.length-1)) {//擴展容量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;}}/** * 得到棧頂元素，但不彈出* @return */public int peek() {if(isEmpty()) {System.out.println("錯誤，棧中元素為空，不能peek");return -1;} else {return tArray[topIndex];}}/** * 判斷當前棧是否為空* @return */public Boolean isEmpty() {return (topIndex < 0);}/** * 打印棧中元素*/public void printElems() {for (int i=0;i<=topIndex;i++) {System.out.print(tArray[i] + " ");}System.out.println();}}3.在一個用鍊錶模擬的隊列ChainQueue
package com.wly.algorithmbase.datastructure;/** * 使用鍊錶實現隊列* * @author wly * */public class ChainQueue {private QueueNode head;// 指向隊列頭節點private QueueNode tail;// 指向隊列尾節點private int size = 0;// 隊列尺寸public ChainQueue() {}/** * 插入新節點到隊列尾*/public void insert(QueueNode node) {// 當然也可以這麼寫,添加tail.prev = node if (head == null) {head = node;tail = head;} else {node.next = tail;tail.prev = node;// 雙向連接，確保head.prev不為空tail = node;}size++;}/** * 移除隊列首節點*/public QueueNode remove() {if (!isEmpty()) {QueueNode temp = head;head = head.prev;size--;return temp;} else {System.out.println("異常操作，當前隊列為空!");return null;}}/** * 隊列是否為空* * @return */public Boolean isEmpty() {if (size > 0) {return false;} else {return true;}}/** * 返回隊列首節點，但不移除*/public QueueNode peek() {if (!isEmpty()) {return head;} else {System.out.println();System.out.println("異常操作，當前隊列為空!");return null;}}/** * 返回隊列大小* * @return */public int size() {return size;}/** * 打印隊列中的元素*/public void printElems() {QueueNode tempNode = head;while(tempNode != null) {System.out.print(tempNode.data + " ");tempNode = tempNode.prev;}System.out.println();}}/** * 節點類* * @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_BFS_DFS
package com.wly.algorithmbase.search;import com.wly.algorithmbase.datastructure.GraphVertex;import com.wly.algorithmbase.datastructure.NoDirectionGraph;/** * 基於圖的深度優先搜索* @author wly * */public class Test_BFS_DFS {public static void main(String[] args) {//初始化測試數據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("--圖的鄰接矩陣--");graph.printIndicatorMat();//測試深搜System.out.println("--深度優先搜索--");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("--廣度優先搜索--");graph.BFS(0);}}這裡測試的圖結構如下:
運行結果如下:
--圖的鄰接矩陣-- 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 --深度優先搜索-- 0 1 0 1 3 0 1 3 6 0 1 4 0 2 0 2 5 --廣度優先搜索-- 0 1 0 1 2 1 2 1 2 3 1 2 3 4 2 3 4 2 3 4 5 3 4 5 3 4 5 6 4 5 6 5 6 6
這裡需要說明一下上面深搜和廣蒐的運行結果，其中0,1,2,3…分別對應著A,B,C,D...有點繞哈，，見諒~~
O啦~~~
總結
以上就是本文關於Java編程實現基於圖的深度優先搜索和廣度優先搜索完整代碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！