广度优先搜索

广度优先搜索可解决两类问题：
第一类问题：从节点A出发，又前往节点B的路径吗？(在你的交际关系网中，有芒果销售商吗？)
第二类问题：从节点A出发，前往节点B的哪条路径最短？(哪个芒光销售商与你的关系最近？)

不管是广度优先遍历一幅有意图还是一棵树，都要用到队列。
首先把起始节点(对树而言是根节点)放入队列。接下来每次从队列的头部取出一个节点，遍历这个节点之后
把它能到达的节点(对树而言是子节点)都依次放入队列。
重复一个队列问题，直到队列中的节点全部被遍历为止。

如果你要找出最快的路径，需要使用另外一种算法。狄克斯特拉算法

狄克斯特拉算法：

1. 找出”最便宜”的节点，即可在最短时间内到达的节点。
2. 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
3. 重复这个过程，直到对图中的每个节点都这么做了。
4. 计算最终路径。

狄克斯特拉算法用于每条边都有关联数字的图，这些数字成为权重。
带权重的图称为加权图，不带权重的图称为非加权图。
要计算非加权图中的最短路径，可使用广度优先搜索。
要计算加权图中的最短路径，可使用狄克斯特拉算法。
狄克斯特拉算法只适用于有向无环图。
贝尔曼-福德算法使用于图中包含负权边。