广度优先搜索算法
介绍
广度优先搜索算法（Breadth-First Search，BFS）是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。
广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：
1.编写国际跳棋AI，计算最少走多少步就可获胜；
2.编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将READED改为READER需要编辑一个地方；
3.根据你的人际关系网络找到关系最近的医生。
两个步骤
使用图来简历问题模型
使用广度优先搜索解决问题
图
图是由顶点的有穷非空集合和顶点之间边的集合组成，通过表示为G(V,E)，其中，G标示一个图，V是图G中顶点的集合，E是图G中边的集合。
无边图：若顶点Vi到Vj之间的边没有方向，则称这条边为无项边（Edge），用序偶对(Vi,Vj)标示。
对于下图无向图G1来说，G1=(V1, {E1})，其中顶点集合V1={A,B,C,D}；边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}:
有向图：若从顶点Vi到Vj的边是有方向的，则成这条边为有向边，也称为弧（Arc）。用有序对（Vi，Vj）标示，Vi称为弧尾，Vj称为弧头。如果任意两条边之间都是有向的，则称该图为有向图。
有向图G2中，G2=（V2,{E2}），顶点集合（A,B,C,D）,弧集合E2={<A,D>,{B,A},<C,A>,<B,C>}.
权：有些图的边和弧有相关的数，这个数叫做权。这些带权的图通常称为网。
广度优先算法
假设你需要去联系你们学院领导，可是你跟他并没有交集啊。此时，你可以去问一圈自己朋友，他们中有没有认识学院领导的。此时，你翻一下自己的通讯录，找找自己有哪些朋友，找到了，万事大吉。没找到，再去看看自己通讯录中的朋友们的通讯录。要先在自己通讯录中找一遍，再去朋友的通讯录，朋友的朋友的通讯录中找。
查找最短路径
广度优先搜索可以回答两类问题
从节点A出发，有前往节点B的路径？
从节点A出发，前往节点B的哪条路径最短？
例如，自己的通讯录是一度关系，朋友的通讯录是二度关系，朋友的朋友的通讯录是三度关系。
在你看来，一度关系超过二度关系，二度关系超过三度关系。因此，你应先在一度关系中搜索，确定其中没有领导后，才在二度关系中搜索。广度优先搜索可是这样做的。
注意 只有按添加顺序查找时，才能实现这样的目的。即使用队列
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
顺序队列
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，如图所示
每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。
顺序队列中的溢出现象：
（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
循环队列
在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。 [2]
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。队空和队满的情况如图：
广度优先搜索算法实现
publicclassbfs{
publicstaticvoidmain(String[]args) {
HashMap<String,String[]>hashMap=newHashMap<String,String[]>();
hashMap.put("YOU",newString[]{"CLAIRE","ALICE","BOB"});
hashMap.put("CLAIRE",newString[]{"YOU","JONNY","THON"});
hashMap.put("JONNY",newString[]{"CLAIRE"});
hashMap.put("THOH",newString[]{"CLAIRE"});
hashMap.put("ALICE",newString[]{"YOU","PEGGY"});
hashMap.put("BOB",newString[]{"YOU","PEGGY","ANUJ"});
hashMap.put("PEGGY",newString[]{"BOB","ALICE"});
hashMap.put("ANUJ",newString[]{"BOB"});
Nodetarget=findTarget("YOU","ANUJ",hashMap);
//打印出最短路径的各个节点信息
printSearPath(target);
}
staticvoidprintSearPath(Nodetarget) {
if(target!=null) {
System.out.print("找到了目标节点:"+target.id+"\n");
List<Node>searchPath=newArrayList<Node>();
searchPath.add(target);
Nodenode=target.parent;
while(node!=null) {
searchPath.add(node);
node=node.parent;
}
Stringpath="";
for(inti=searchPath.size()-1;i>=0;i--) {
path+=searchPath.get(i).id;
if(i!=0) {
path+="-->";
}
}
System.out.print("步数最短："+path);
}else{
System.out.print("未找到了目标节点");
}
}
staticNodefindTarget(StringstartId,StringtargetId,HashMap<String,String[]>map) {
List<String>hasSearchList=newArrayList<String>();
LinkedBlockingQueue<Node>queue=newLinkedBlockingQueue<Node>();
//Queue 中 在容量已满的情况下 add()方法会抛出IIIegalStateException异常，offer()方法只会返回false
queue.offer(newNode(startId,null));
while(!queue.isEmpty()) {
//poll()和remove()都将移除并且返回队头，但是在poll()在队列为空时返回null, 而remove()会抛出NoSuchElementException异常。
Nodenode=queue.poll();
if(hasSearchList.contains(node.id)) {
continue;
}
System.out.print("判断节点:"+node.id+"\n");
if(targetId.equals(node.id)) {
returnnode;
}
hasSearchList.add(node.id);
if(map.get(node.id)!=null&&map.get(node.id).length>0) {
for(StringchildId:map.get(node.id)) {
queue.offer(newNode(childId,node));
}
}
}
returnnull;
}
}
classNode{
publicStringid;
publicNodeparent;
publicNode(Stringid,Nodeparent) {
this.id=id;
this.parent=parent;
}
}
