另一方面，Breadth-First Search，BFS )是一种盲目搜索方法，旨在系统地展开和检查图中的所有节点，寻找结果。 也就是说，不考虑结果的可能位置，而是彻底搜索整个图直到找到结果。 BFS不使用经验法则算法。
在广度优先搜索中，可以找到两个东西之间的最短距离，但最短距离的意义有很多！ 使用广度优先搜索，可以执行以下操作：
创建国际棋盘格AI，创建拼写检查器，计算最少走几步就能赢，然后计算编辑多少处才能将拼写错误的单词更改为正确的单词。 例如，要将READED更改为READER，必须编辑一个位置。 根据你的人际关系网找到最近的医生。 二、假设你住在旧金山，从双子峰去金门大桥。 我想坐巴士去，希望换乘最少。 能乘坐的巴士如下。
为了找到换乘最少的乘车路线，用什么算法？
一步能到达金门大桥吗？ 下面强调了一步能走的地方。
金门大桥不突出，所以一步也到不了那里。 两步可以吗？
金门大桥也不突出，所以两步都到不了。 三步走？
金门大桥突出！ 所以从双子峰出发，沿着下面的路线三步就到金门大桥。
虽然还有其他通往金门大桥的路线，但是它们更远(需要四步)。 该算法发现，通往金门大桥的最短路径需要三步。 这种问题被称为最短路径问题(shorterst-path problem )。 你必须经常找到最短的路径。 这可能是去朋友家的最短路径，也可能是下国际象棋堵塞对方的最低手续费。 解决最短路径问题的算法称为幅度优先搜索。 要决定如何从双子峰去金门大桥，需要两个步骤。
(1)用图建立问题模型。
(2)使用广度优先搜索解决问题。
下面介绍什么是图，然后详细讨论广度优先搜索。
三、图由顶点的无穷非空集合和顶点间的边的集合组成，用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}。
权：有些图的边和弧有相关的数，这个数叫权。 这些带权利的图通常被称为网。
四、广度优先搜索算法假设你在经营芒果农场，你需要找芒果销售商把芒果卖给他。 你在脸书上和芒果经销商有联系吗？ 为此，你可以在朋友中寻找。
这个搜索很简单。 首先，列一个朋友列表。
然后，按顺序检查名单上的所有人，看看是否是芒果销售商。
如果没有芒果销售商的朋友，就必须在朋友的朋友中找。
检查名单上的所有人时，你会把那个朋友添加到名单上。
那样的话，你不仅在朋友中找，在朋友中也找。 请不要忘记。 你的目标是在你的人际关系网上找到芒果销售商。 因此，如果鳗鱼红牛不是芒果销售商，它的朋友也会被列入名单。 这意味着你要在她的朋友、朋友的朋友等中寻找。 使用该算法搜索你的整个人际关系网，直到找到芒果销售商。 这就是广度优先搜索算法。
五.找最短的路线再说一遍。 宽度优先搜索可以回答两种问题。
类型1问题：是否有从节点a出发到节点b的路径？ )你的人际关系网上有芒果经销商吗？ ）
类型2问题：从节点a出发到节点b的哪个路径最短？ 哪个芒果经销商和你关系最近？ ）
我刚才看到了怎么回答第一个问题，让我们来回答第二个问题——吧。 最近的芒果经销商是谁？ 例如，朋友是一次关系，朋友的朋友是两次关系。
在你看来，一次关系胜于二次关系，二次关系胜于三次关系，由此类推。 因此，请搜索一次关系，确保没有芒果销售商，然后再搜索两次关系。 广度优先搜索就是这样做的！ 在宽度优先搜索的执行中，搜索范围从起点逐渐向外侧延伸。 也就是说，先检查一次关系，再检查两次关系。 顺便问一下，你先检查tzdmt还是Anuj？ tzdmt是一次关系，Anuj是二次关系
它首先检查tzdmt，然后检查Anuj。
也可以这样看。 一次关系在两次关系之前加入搜索列表。
请按顺序检查名单上的所有人，看看他是否是芒果销售商。 因为这是一次关系找，然后是两次关系找，所以找到的是最有关系的芒果经销商。 宽度优先搜索不仅找到从a到b的路径，还找到最短的路径。
请注意，只有按添加顺序搜索才能实现此目的。 改变句子
话说，如果tzdmt先于Anuj加入名单，就需要先检查tzdmt，再检查Anuj。如果tzdmt和Anuj都是芒果销售商，而你先检查Anuj再检查tzdmt，结果将如何呢？找到的芒果销售商并非是与你关系最近的，因为Anuj是你朋友的朋友，而tzdmt是你的朋友。因此，你需要按添加顺序进行检查。有一个可实现这种目的的数据结构，那就是队列（queue）。 六、队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（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。队空和队满的情况如图：
七、广度优先搜索算法实现我们要从“你”出发找到“ANUJ”，关系表示为下图，使用广度优先搜索算法
先概述一下这种算法的工作原理。
但这样可能会出现一些问题，axdds既是鳗鱼红牛的朋友又是xfd的朋友，因此她将被加入队列两次：一次是在添加鳗鱼红牛的朋友时，另一次是在添加xfd的朋友时。因此，搜索队列将包含两个axdds。
但你只需检查axdds一次，看她是不是芒果销售商。如果你检查两次，就做了无用功。因此，检查完一个人后，应将其标记为已检查，且不再检查他。
如果不这样做，就可能会导致无限循环。假设你的人际关系网类似于下面这样。
一开始，搜索队列包含你的所有邻居。
现在你检查axdds。她不是芒果销售商，因此你将其所有邻居都加入搜索队列。
接下来，你检查自己。你不是芒果销售商，因此你将你的所有邻居都加入搜索队列。
以此类推。这将形成无限循环，因为搜索队列将在包含你和包含axdds之间反复切换。
检查一个人之前，要确认之前没检查过他，这很重要。为此，你可使用一个列表来记录检查过的人。
首先，需要使用代码来实现图。图由多个节点组成。
每个节点都与邻近节点相连，如果表示类似于“你→xfd”这样的关系呢？好在你知道的一种结构让你能够表示这种关系，它就是散列表！
记住，散列表让你能够将键映射到值。在这里，你要将节点映射到其所有邻居。
图不过是一系列的节点和边，因此在JAVA中，你可以使用HashMap来表示一个图。
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.concurrent.LinkedBlockingQueue;public class BFS { public static void main(String[] args) { HashMap<String,String[]> hashMap=new HashMap<>(); hashMap.put("YOU",new String[]{"ldfy","淡定的月光","BOB"}); hashMap.put("ldfy",new String[]{"YOU","JONNY","THON"}); hashMap.put("JONNY",new String[]{"ldfy"}); hashMap.put("THOH",new String[]{"ldfy"}); hashMap.put("淡定的月光",new String[]{"YOU","PEGGY"}); hashMap.put("BOB",new String[]{"YOU","PEGGY","ANUJ"}); hashMap.put("PEGGY",new String[]{"BOB","淡定的月光"}); hashMap.put("ANUJ",new String[]{"BOB"}); Node target = findTarget("YOU","ANUJ",hashMap); //打印出最短路径的各个节点信息 printSearPath(target); } /** * 打印出到达节点target所经过的各个节点信息 * @param target */ static void printSearPath(Node target) { if (target != null) { System.out.print("找到了目标节点:" + target.id + "n"); List<Node> searchPath = new ArrayList<Node>(); searchPath.add(target); Node node = target.parent; while(node!=null) { searchPath.add(node); node = node.parent; } String path = ""; for(int i=searchPath.size()-1;i>=0;i--) { path += searchPath.get(i).id; if(i!=0) { path += "-->"; } } System.out.print("步数最短："+path); } else { System.out.print("未找到了目标节点"); } } static Node findTarget(String startId,String targetId,HashMap<String,String[]> map) { List<String> hasSearchList = new ArrayList<String>(); LinkedBlockingQueue<Node> queue=new LinkedBlockingQueue<>(); queue.offer(new Node(startId,null)); while(!queue.isEmpty()) { Node node = queue.poll(); if(hasSearchList.contains(node.id)) { continue; } System.out.print("判断节点:" + node.id +"n"); if (targetId.equals(node.id)) { return node; } hasSearchList.add(node.id); if (map.get(node.id) != null && map.get(node.id).length > 0) { for (String childId : map.get(node.id)) { queue.offer(new Node(childId,node)); } } } return null; } static class Node{ public String id; public Node parent; public Node(String id,Node parent) { this.id = id; this.parent = parent; } }} 运行时间如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一个人到另一个人的箭头或连接），因此运行时间至少为O(边数)。
你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为O(1)，因此对每个人都这样做需要的总时间为O(人数)。所以，广度优先搜索的运行时间为O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。