图的遍历（2）—广度优先遍历
图的遍历（二）—广度优先遍历
上一节中写了图的深度优先遍历，http://blog.****.net/wtyvhreal/article/details/43305785
这一节讲解下图的广度优先遍历。
同样的图：
广度优先遍历的顺序结果如下：
广度优先遍历的思想：
首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点，然后对每个相邻的顶点，再访问他们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。
队列遍历示意图：
输入数据：
运行结果：
图的广度优先遍历应用——最少转机
1号城市坐飞机到5号城市，希望找到一种乘坐方式，使得转机的次数最少。
输入数据：
运行结果：
当然也可以用深度优先遍历解决，但是这里用广度优先遍历会更快。
广度优先遍历更加适用于所有边的权值相同的情况。