广度优先搜索

图的遍历：从图中某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次

广度优先搜索(BFS)：
1）首先访问起始顶点v
2）接着由v出发依次访问v的各个未被访问过的邻接顶点w1，w2…wi
3）然后依次访问w1，w2…wi的所有未被访问过的邻接顶点
4）从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，以此类推

BFS算法的性能分析：
1）空间复杂度：O(|V|)
2）时间复杂度：邻接矩阵法O(|V|^2)，邻接表法O(|V|+|E|)

无权图单源最短路径问题：定义从顶点u到顶点v的最短路径d(u,v)为从u到v的任何路径中最少的边数，若从u到v没有通路，则d(u,v)=正无穷

广度优先生成树：在广度遍历过程中，我们可以得到一棵遍历树，称为广度优先生成树(生成森林)【邻接矩阵法的广度优先生成树唯一，邻接表法的不唯一】