广度优先搜索算法，项目实战北京地图/贪心学院

北京很大，附上地铁图，不要迷路！！！

AI广度优先搜索算法，项目实战北京地图

作为一个程序员，在北京，你很有可能住在回龙观地区，经常从龙泽上地铁，然后畅游北京。

当有一天，你老家的朋友来北京了，希望你能够带她去天安门玩一玩，你该怎么坐地铁呢？

AI广度优先搜索算法，项目实战北京地图

基本要求，我们乘坐地铁，绿色出行，但希望换乘的最少。

此时，有可能你并不懂广度优先搜索算法，但实际上你已经运用了它。

找出从龙泽到天安门东的最短路径问题，就叫做广度优先搜索

下图列除了部分可以到达的路线：

AI广度优先搜索算法，项目实战北京地图

从龙泽前往天安门东的最短路径需要三步，这种问题被称之为最短路径问题，那么解决最短路径问题的算法被称之为广度优先搜索

是不是这种概念，非常容易理解。

那我们进一步对广度优先搜索进行一个说明：

• 广度优先搜索是一种用于图的查找算法，可以解决两类问题
• 从节点A出发，能够到达节点B么！
• 从节点A出发，前往节点B的路径中，最短的是哪条路径！

举个

金融场景下，借款人A到平台借款，逾期未还，假定我们知道他的朋友中（朋友13）会帮助他还，这个例子可能不是特别的恰当，但可以帮助大家说明问题，并深入理解广度优先搜索

AI广度优先搜索算法，项目实战北京地图

广度优先搜索，不仅查找从借款人A到朋友13的路径，而且找到的是最短路径，为什么要找到最短路径呢，原因是图关系中，越近找到，说明关系越紧密。

如果你懂知识图谱技术的话，那可能直接用最短路径算法，就可以直接获取到。那么不用知识图谱的图计算技术，就可以用到队列的技术来实现

AI广度优先搜索算法，项目实战北京地图 AI广度优先搜索算法，项目实战北京地图 AI广度优先搜索算法，项目实战北京地图 AI广度优先搜索算法，项目实战北京地图

那么这里需要注意一个问题，这个问题就是当执行到朋友1时，要把借款人自己给去除掉，否则就变成了死循环了

AI广度优先搜索算法，项目实战北京地图 AI广度优先搜索算法，项目实战北京地图

最后的总结：

• 广度优先搜索指出是否有从A到B的路径
• 广度优先搜索将会找出最短路径
• 可以先创建图，然后再根据图关系使用广度优先搜索算法来解决问题
• 你需要按照加入的顺序去检查，否则找到的不是最短路径，因此如果你用的不是知识图谱的图算法技术，那么就必须是队列
• 对于检查过的人，就不要再检查了，否则会造成死循环