图的广度优先搜索（BFS）算法：
基本概念：
对于给定的图G=(V,E),广度优先搜索从一个源顶点出发，通过对其邻接表进行遍历(搜索)，可以发现所有与源顶点邻接的顶点。依次类推，不断地向外扩展，进而发现与源顶点的邻接点相邻接的顶点。故得名广度优先搜索(BFS);
算法思想：
为了标记一个顶点是否被发现，其邻接表是否已经被扫描，广度优先搜索采用三种颜色进行标识，即白色、灰色和黑色。
1. 如果一个顶点没有被发现，则其颜色为白色；（未入队列）
2. 如果一个顶点已经被发现而邻接表未被搜索，则其为灰色；（已入队列）
3. 如果一个顶点的邻接表已经被扫描完，则其为黑色；（已出队列）
在扫描一个顶点u的邻接表的过程中，如果发现了一个白色顶点v，则称u为v的父亲节点。由于一个顶点的邻接点一般有多个，为了表示这些邻接点被当前节点（其父节点）发现的顺序，需要借助于队列；对于先发现的节点先入队列（同时意味着先出队列）；
应用：在广度优先搜索的过程中，可以记录一些重要的额外信息，如当前节点的父亲节点（用于回溯路径）、源节点到当前节点的距离（用于求最短路径）等。
BFS源码剖析（算法导论版）
广度优先搜索的代码主要包括两个部分，第一部分为初始化，主要是对所有的节点进行着色、父亲节点置空，距离置零等，如下所示：
广度优先搜索的代码第二部分是主循环部分，循环终止条件是队列为空，代码核心是对当前出队的节点（灰色节点）的邻接表进行扫描以发现白色节点。如下图所示：
广度优先搜索的时间复杂度分析:
由于每个节点仅被发现一次，因此每个节点入栈和出栈各一次，时间均为O(1),故入栈和出栈总时间为O(V);由于需要对每个节点的邻接表进行扫描，时间为O(Adj[u]),总时间为O(E);综上所示，广度优先搜索的时间复杂度为O(V+E).即是图邻接表大小的线性函数。
广度优先树和最短路径(Shortest Path):
广度优先搜索的过程会产生一个广度优先树(BST),从源顶点s到当前节点v的最短路径是从s到v所有路径中边数最少的那条。如果两个顶点没有路径，即不可达，则最短路径为无穷大。
在此不加证明地给出：广度优先搜索所计算出的距离即为源顶点到当前节点的最短距离。通过从当前节点的父亲域进行回溯即可获得最短路径。代码如下：