广度优先算法.md

广度优先搜索（BFS），可以被形象的描述为“浅尝辄止”，具体一点就是每个顶点只访问它的邻接节点（如果它的邻接节点没有被访问）并且记录这个邻接节点，当访问完它的邻接节点之后就结束这个顶点的访问。 广度优先用到了“先进先出”队列，通过这个队列来存储第一次发现的节点，以便下一次的处理；而对于再次发现的节点，我们不予理会——不放入队列，因为再次发现的节点： 无非是已经处理完的了； 或者是存储在队列中尚未处理的。

广度优先算法尽可能的靠近顶点 ，然后再访问较远的区域。下面几条规则：

• 规则1、访问下一个邻接点（如果存在），这个顶点必须是当前顶点的邻接点，标记他并把它插入队列。
• 规则2、如果因为没有访问的顶点而无法执行规则1时，那么就从队列的头取出一个顶点（如果存在）作为当前顶点。
• 规则3、如果因为队列为空而不能执行规则2，则搜索结束。

/**
 * @author hasee
 * @TIME 2017年5月3日
 */
public class Breadth {
	public static void main(String[] args){
		Grap theGraph = new Grap();
		theGraph.addVert('A');
		theGraph.addVert('B');
		theGraph.addVert('C');
		theGraph.addVert('D');
		theGraph.addVert('E');
		theGraph.addEdge(0, 1);//AB
		theGraph.addEdge(1, 2);//BC
		theGraph.addEdge(0, 3);//AD
		theGraph.addEdge(3, 4);//DE
		theGraph.bfs();
	}
}
/**
 * @author hasee
 * @TIME 2017年5月3日
 * 实现简单的队列
 */
class Queue{
	private final int SIZE = 20;
	private int[] queArry;
	private int front;
	private int rear;
	public Queue(){
		queArry = new int[SIZE];
		front = 0;
		rear = -1;
	}
	public void insert(int j){
		if(rear == SIZE -1)
			rear = -1;
		queArry[++rear] = j;
	}
	public int remove(){
		int tmp = queArry[front++];
		if(front == SIZE)
			front = 0;
		return tmp;
	}
	public  boolean isEmpty(){
		return (rear+1==front||front+SIZE-1 == rear);
	}
}
class Vert{
	public char label;
	public boolean wasVisited;
	public Vert(char lab){
		this.label = lab;
		this.wasVisited = false;
	}
}
class Grap{
	private final int MAX_VRERTS = 20;
	private Vert vertxList[];//包含所有的节点信息
	private int adjMat[][];//邻接矩阵
	private int nVert;//当前vertxList的指向下标
	private Queue	 theaqueue;
	public Grap(){
		vertxList = new Vert[MAX_VRERTS];
		adjMat = new int[MAX_VRERTS][MAX_VRERTS];
		nVert = 0;
		for(int j=0;j<MAX_VRERTS;j++)
			for(int k = 0;k<MAX_VRERTS;k++)
				adjMat[j][k] = 0;
		theaqueue = new Queue();
	}
	public void addVert(char lab){
		vertxList[nVert++] = new Vert(lab);
	}
	/**
	 * @param start
	 * @param end
	 * 邻接矩阵，添加课执行的
	 */
	public void addEdge(int start,int end){
		adjMat[start][end] = 1;
		adjMat[end][start] = 1;
	}
	/**
	 * @param v
	 * 展示节点数值
	 */
	public void display(int v){
		System.out.println(vertxList[v].label);
	}
	/**
	 * 广度优先算法和深度优先算法类似，只是用队列代替了栈，嵌套循环代替了单层循环。
	 * 外层循环等待队列为空，而内层循环依次寻找当前顶点的未访问的邻接点。
	 */
	public void bfs(){
			vertxList[0].wasVisited = true;
			display(0);
			theaqueue.insert(0);
			int v2;
			//外层循环用来判断队列是否为空
			while(!theaqueue.isEmpty()){
				int v1 = theaqueue.remove();//弹出作为顶点
				//内层循环去找当前节点的邻接点
				while((v2 = getAdjUnivisitedVertx(v1)) != -1){
					vertxList[v2].wasVisited = true;
					display(v2);
					theaqueue.insert(v2);
				}
			}
			//重置访问标志
			for(int j=0;j<nVert;j++){
				vertxList[j].wasVisited =false;
			}
	}
	/**
	 * @param v
	 * @return
	 * 广度优先算法关键是找到邻接且没有被访问过的点。
	 */
	public  int getAdjUnivisitedVertx(int v){
		for(int i=0;i<nVert;i++){
			if(adjMat[v][i] == 1 &&vertxList[i].wasVisited == false)
				return i;
		}
		return -1;
	}
}