Java编程实现基于图的深度优先搜索和广度优先搜索完整代码

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();			}		}	}}

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();	}}

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 + "";	}}

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