广度优先搜索算法
/
介绍
广度优先算法按照一种同心圆的方式，首先访问所有和初始顶点邻接的顶点，然后访问与邻接节点邻接的所有未访问到的节点，以此类推，直到所有与初始顶点同在一个连通分量中的顶点都访问过了为止。如果图中仍然存在未被访问的节点，该算法必须从图的其他连通分量中的任意顶点重新开始。
使用队列来跟踪广度优先搜索的操作是比较方便的，该队列先从遍历的初始顶点开始，将该顶点标记为已访问。在每次迭代的时候，该算法找出所有和队头顶点邻接的未访问节点，并将它们标记为已访问，再把它们入队，然后将队头节点从队列中移除(因为该节点所有可能的下一步已经在队列中，该节点被pass)。
上述介绍比较难懂，广度优先算法致力于解决的问题可以概括为：在一个图中已知起点与终点，求从起点出发到终点的最短路径。起点即初始节点，终点为目标节点，从初始节点出发开始广度优先遍历搜索，第一次到达目标节点时走过的路径即位最短路径。