Java如何實現(xiàn)基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索

這篇文章將為大家詳細講解有關Java如何實現(xiàn)基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

1.新建一個表示“無向圖”類NoDirectionGraph

package com.wly.algorithmbase.datastructure;
/** 
 * 無向圖 
 * @author wly 
 * 
 */
public class NoDirectionGraph {
	private int mMaxSize;
	//圖中包含的最大頂點數(shù) 
	private GraphVertex[] vertexList;
	//頂點數(shù)組 
	private int[][] indicatorMat;
	//指示頂點之間的連通關系的鄰接矩陣 
	private int nVertex;
	//當前實際保存的頂點數(shù)目 
	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("---插入失敗，頂點數(shù)量已達上限!");
		}
	}
	/** 
   * 修改鄰接矩陣，添加新的邊 
   * @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();
		}
	}
	/** 
   * 深度優(yōu)先遍歷 
   * @param vertexIndex 表示要遍歷的起點,即圖的鄰接矩陣中的行數(shù) 
   */
	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();
			}
			//檢索當前棧頂元素是否包含其他未遍歷過的節(jié)點 
			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;
	}
	/** 
   * 廣度優(yōu)先遍歷 
   * @param vertexIndex 表示要遍歷的起點,即圖的鄰接矩陣中的行數(shù) 
   */
	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.然后是一個用數(shù)組模擬的棧ArrayStack

package com.wly.algorithmbase.datastructure;
/** 
 * 使用數(shù)組實現(xiàn)棧結構 
 * @author wly 
 * 
 */
public class ArrayStack {
	private int[] tArray;
	private int topIndex = -1;
	//表示當前棧頂元素的索引位置 
	private int CAPACITY_STEP = 12;
	//數(shù)組容量擴展步長 
	public ArrayStack() {
		/***創(chuàng)建泛型數(shù)組的一種方法***/
		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;
/** 
 * 使用鏈表實現(xiàn)隊列 
 * 
 * @author wly 
 * 
 */
public class ChainQueue {
	private QueueNode head;
	// 指向隊列頭節(jié)點 
	private QueueNode tail;
	// 指向隊列尾節(jié)點 
	private int size = 0;
	// 隊列尺寸 
	public ChainQueue() {
	}
	/** 
   * 插入新節(jié)點到隊列尾 
   */
	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++;
	}
	/** 
   * 移除隊列首節(jié)點 
   */
	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;
		}
	}
	/** 
   * 返回隊列首節(jié)點，但不移除 
   */
	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();
	}
}
/** 
 * 節(jié)點類 
 * 
 * @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;
/** 
 * 基于圖的深度優(yōu)先搜索 
 * @author wly 
 * 
 */
public class Test_BFS_DFS {
	public static void main(String[] args) {
		//初始化測試數(shù)據(jù) 
		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("--深度優(yōu)先搜索--");
		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("--廣度優(yōu)先搜索--");
		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  
--深度優(yōu)先搜索-- 
0 1  
0 1 3  
0 1 3 6  
0 1 4  
0 2  
0 2 5  
--廣度優(yōu)先搜索-- 
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

關于“Java如何實現(xiàn)基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。