【数据结构】Java实现图的深度优先搜索与广度优先搜索

在图中实现的基本操作之一就是搜索从一个顶点可以到达其他哪些顶点，或者找所有当前顶点可到达的顶点。有两种常用的方法可用来搜索图：深度优先搜索（DFS）和广度优先搜索（BFS），它们最终都会到达所有的连通顶点。深度优先搜索通过栈来实现（类似于树的前序遍历，树的前序遍历就是深度优先搜索的特殊版本），而广度优先搜索通过队列来实现（类似于树的层次遍历，树的层次遍历就是广度优先搜索的特殊版本）。具体的见下面的程序：

1. 图的存储结构为邻接矩阵

package graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction;



/**
 * 存储结构为邻接矩阵
 * @author Administrator
 *
 */
public class Graph1 {
	class Vertex{//顶点类
		public String  data;
		public boolean isVisted;
		
		public Vertex(String data) {
			this.data = data;
			isVisted = false;
		}
	}
	
	public final static int MAX_VERTEX = 25;//顶点个数最大值
	public Vertex[] vertexArray;//顶点表
	public boolean[][] edgeArray;//邻接矩阵
	public int verNum;
	public Stack<Integer> stack;
	public Queue<Integer> queue;
	
	//初始化图
	public Graph1() {
		vertexArray = new Vertex[MAX_VERTEX];
		edgeArray = new boolean[MAX_VERTEX][MAX_VERTEX];
		verNum = 0;
		
		for(int i = 0; i < MAX_VERTEX; i ++) 
			for(int j = 0; j < MAX_VERTEX; j ++) 
				edgeArray[i][j] = false;
		
		stack = new Stack<>();
		queue = new LinkedList<>();
			
	}
	
	//增加顶点
	public void addVertex(String data) {
		vertexArray[verNum ++] = new Vertex(data);
	}
	
	//增加边
	public void addEdge(int start , int end) {
		edgeArray[start - 1][end - 1] = true;
		edgeArray[end - 1][start - 1] = true;
	}
	
	/**非递归
     * 深度优先搜索算法:做四件事
     * 1. 用peek()方法检查栈顶的顶点
     * 2. 试图找到这个顶点还未访问的邻节点
     * 3. 如果没有找到，出栈
     * 4. 如果找到这样的顶点，访问这个顶点，并把它放入栈
     * 深度优先算法类似于从树的跟逐个沿不同路径访问到不同的叶节点
     */
	public void DFS() {
		System.out.print(vertexArray[0].data + " ");
		vertexArray[0].isVisted = true;		
		stack.push(0);
		while(!stack.isEmpty()) {
			int v = getUnvistedVertex(stack.peek());
			if(v == -1) {
				stack.pop();
			}else {
				System.out.print(vertexArray[v].data + " ");
				vertexArray[v].isVisted = true;	
				stack.push(v);
			}
		}
		//清除遍历印记
		for(int i = 0; i < verNum; i ++) {
			vertexArray[i].isVisted = false;
		}
	}
		 
	//任意图的递归深度优先搜索
	public void DFS1() {
		for(int i = 0; i < verNum; i ++)
			if(!vertexArray[i].isVisted)
				DFS1(i);
		
		//清除遍历印记
		for(int k = 0; k < verNum; k ++) {
			vertexArray[k].isVisted = false;
		}
	}
	//连通图的递归深度优先搜索
	private void DFS1(int i){
		System.out.print(vertexArray[i].data + " ");
		vertexArray[i].isVisted = true;
		for(int j = 0;j < verNum; j ++) {
			if(edgeArray[i][j] && !vertexArray[j].isVisted)
				DFS1(j);
		}
	}
	
	/**
     * 广度优先搜索算法：做四件事
     * 1. 用remove()方法检查栈顶的顶点
     * 2. 试图找到这个顶点还未访问的邻节点
     * 3. 如果没有找到，该顶点出列
     * 4. 如果找到这样的顶点，访问这个顶点，并把它放入队列中
     * 深度优先算法中，好像表现的要尽快远离起始点，在广度优先算法中，要尽可能靠近起始点。
     * 它首先访问其实顶点的所有邻节点，然后再访问较远的区域。这种搜索不能用栈，而要用队列来实现。
     * 广度优先算法类似于从树的跟逐层往下访问直到底层
     */
	public void BFS() {
		vertexArray[0].isVisted = true;
		System.err.print(vertexArray[0].data + " ");
		queue.add(0);
		int v2;
		while(!queue.isEmpty()) {
			int v1 = queue.remove();
			while((v2 = getUnvistedVertex(v1)) != -1) {
				vertexArray[v2].isVisted = true;
				System.out.print(vertexArray[v2].data + " ");
				queue.add(v2);
			}
		}
		//清除遍历印记
		for(int i = 0; i < verNum; i ++) {
			vertexArray[i].isVisted = false;
		}
	}
	
	//获取与v1相连且未遍历顶点在定点表中的下标
	private int getUnvistedVertex(int v1) {
		for(int j = 0; j < verNum; j ++)
			if(edgeArray[v1][j] && !vertexArray[j].isVisted)
				return j;
		return -1;
	}

	public static void main(String[] args) {
		Graph1 graph = new Graph1();

		graph.addVertex("a");
		graph.addVertex("b");
		graph.addVertex("c");
		graph.addVertex("d");
		graph.addVertex("e");
		/**
		 *                   a
		 *                  / \
		 *                 /   \
		 *                b ——— d
		 *				 /       \
		 *              e         c
		 */              
		graph.addEdge(1, 2);
		graph.addEdge(1, 4);
		graph.addEdge(2, 4);
		graph.addEdge(2, 5);
		graph.addEdge(3, 4);
		
		System.out.print("DFS1:");
		graph.DFS1();
		System.out.println();
		
		System.out.print("DFS:");
		graph.DFS();
		System.out.println();
		
		System.out.print("BFS:");
		graph.BFS();
		
		
		
	}
}